JAVA

// 剩余容量为0，上界即当前价值（文档逻辑）
       import java.util.*;

       /**
        * 物品类：存储重量和价值，按单位价值（p/w）降序排序（文档核心预处理步骤）
        */
       class KnapsackItem {
           int weight;  // 物品重量（对应文档中的w）
           int value;   // 物品价值（对应文档中的p）

           public KnapsackItem(int weight, int value) {
               this.weight = weight;
               this.value = value;
           }

           // 文档要求：按单位价值降序排序（用整数交叉乘法避免浮点数误差）
           public static Comparator<KnapsackItem> byValuePerWeightDesc = (item1, item2) -> {
               // 单位价值：item1.p/item1.w > item2.p/item2.w 等价于 item1.p*item2.w > item2.p*item1.w
               return item2.value * item1.weight - item1.value * item2.weight;
           };
       }

       /**
        * 活结点类：存储搜索过程中的待扩展结点（文档中的“待处理结点表PT”元素）
        * 支持按上界（ub）降序排序（文档要求“优先扩展上界最大的结点”）
        */
       class ActiveNode implements Comparable<ActiveNode> {
           int currentWeight;  // 当前背包重量（文档中的w）
           int currentValue;   // 当前背包价值（文档中的v）
           int nextItemIndex;  // 下一个待处理物品的索引（避免重复处理）
           double upperBound;  // 结点上界（文档中的ub，限界函数计算结果）

           public ActiveNode(int currentWeight, int currentValue, int nextItemIndex, double upperBound) {
               this.currentWeight = currentWeight;
               this.currentValue = currentValue;
               this.nextItemIndex = nextItemIndex;
               this.upperBound = upperBound;
           }

           // 文档要求：优先队列按上界降序取结点（Java默认最小堆，需反转比较逻辑）
           @Override
           public int compareTo(ActiveNode other) {
               return Double.compare(other.upperBound, this.upperBound);
           }
       }

       /**
        * 分支限界法求解0/1背包问题（完全遵循《陈慧文.doc》算法逻辑）
        */
       public class BnBKnapsackSolution {

           /**
            * 限界函数（文档定义）：ub = 已得价值 + (剩余容量) × 后续最高单位价值
            * 作用：估算结点能达到的最大价值，用于剪枝和优先队列排序
            */
           private static double calculateUpperBound(int currentWeight, int currentValue, int nextItemIndex,
                                                     KnapsackItem[] sortedItems, int capacity) {
               int remainingCapacity = capacity - currentWeight;
               double upperBound = currentValue;

               // 剩余容量为0，上界即当前价值（文档逻辑）
               if (remainingCapacity <= 0) {
                   return upperBound;
               }

               // 按单位价值降序累加后续物品（允许 fractional 装法，保证上界不低于真实最优值）
               for (int i = nextItemIndex; i < sortedItems.length; i++) {
                   KnapsackItem item = sortedItems[i];
                   if (item.weight <= remainingCapacity) {
                       // 能装下整个物品，直接加价值
                       upperBound += item.value;
                       remainingCapacity -= item.weight;
                   } else {
                       // 装不下整个物品，按比例加价值（文档中的fractional处理）
                       upperBound += (double) remainingCapacity * item.value / item.weight;
                       break;  // 后续物品单位价值更低，无需继续计算
                   }
               }
               return upperBound;
           }

           /**
            * 核心算法：分支限界法求解指定0/1背包实例（N=3，W=(16,15,15)，P=(45,25,25)，C=30）
            */
           public static int solveKnapsack(KnapsackItem[] originalItems, int capacity) {
               // 步骤1：按单位价值降序排序物品（文档实验内容的核心预处理，保证限界函数有效）
               KnapsackItem[] sortedItems = originalItems.clone();
               Arrays.sort(sortedItems, KnapsackItem.byValuePerWeightDesc);

               // 步骤2：初始化优先队列（文档中的“待处理结点表PT”），存入根结点
               PriorityQueue<ActiveNode> activeNodesQueue = new PriorityQueue<>();
               double rootUb = calculateUpperBound(0, 0, 0, sortedItems, capacity);
               activeNodesQueue.offer(new ActiveNode(0, 0, 0, rootUb));

               // 步骤3：初始化当前最优值（文档中的“下界down”，初始为0）
               int maxValue = 0;

               // 步骤4：循环扩展活结点（文档中的“循环直到叶子结点为PT中最大值”）
               while (!activeNodesQueue.isEmpty()) {
                   // 取出上界最大的活结点（文档要求“优先扩展最有希望的结点”）
                   ActiveNode currentNode = activeNodesQueue.poll();

                   // 剪枝：上界≤当前最优值，其子树无更优解（文档剪枝策略）
                   if (currentNode.upperBound <= maxValue) {
                       continue;
                   }

                   // 所有物品处理完毕（叶子结点），更新最优值
                   if (currentNode.nextItemIndex == sortedItems.length) {
                       if (currentNode.currentValue > maxValue) {
                           maxValue = currentNode.currentValue;
                       }
                       continue;
                   }

                   // 处理下一个物品（文档中的“分支”：装或不装）
                   KnapsackItem nextItem = sortedItems[currentNode.nextItemIndex];
                   int nextIndex = currentNode.nextItemIndex + 1;

                   // 分支1：装入下一个物品（文档中的“左分支”）
                   int newWeight1 = currentNode.currentWeight + nextItem.weight;
                   int newValue1 = currentNode.currentValue + nextItem.value;
                   if (newWeight1 <= capacity) {  // 不超重则保留
                       double ub1 = calculateUpperBound(newWeight1, newValue1, nextIndex, sortedItems, capacity);
                       if (ub1 > maxValue) {  // 上界>当前最优值，加入PT（文档步骤3.2）
                           activeNodesQueue.offer(new ActiveNode(newWeight1, newValue1, nextIndex, ub1));
                       }
                   }

                   // 分支2：不装入下一个物品（文档中的“右分支”）
                   int newWeight2 = currentNode.currentWeight;
                   int newValue2 = currentNode.currentValue;
                   double ub2 = calculateUpperBound(newWeight2, newValue2, nextIndex, sortedItems, capacity);
                   if (ub2 > maxValue) {  // 上界>当前最优值，加入PT（文档步骤3.2）
                       activeNodesQueue.offer(new ActiveNode(newWeight2, newValue2, nextIndex, ub2));
                   }
               }

               return maxValue;
           }

           // 测试：仅针对《陈慧文.doc》中指定的0/1背包实例（N=3，W=(16,15,15)，P=(45,25,25)，C=30）
           public static void main(String[] args) {
               // 初始化目标实例（文档中的实验内容参数）
               KnapsackItem[] items = {
                       new KnapsackItem(16, 45),  // 物品1：w=16，p=45
                       new KnapsackItem(15, 25),  // 物品2：w=15，p=25
                       new KnapsackItem(15, 25)   // 物品3：w=15，p=25
               };
               int capacity = 30;  // 背包容量C=30

               // 求解并输出结果
               int optimalValue = solveKnapsack(items, capacity);
               System.out.println("《陈慧文.doc》0/1背包实例求解结果：");
               System.out.println("背包容量：" + capacity);
               System.out.println("物品重量：(16, 15, 15)");
               System.out.println("物品价值：(45, 25, 25)");
               System.out.println("最优解总价值：" + optimalValue);  // 预期结果：50（装入物品2和3）
               System.out.println("最优装入方案：不装物品1，装入物品2和物品3（总重量15+15=30）");
           }
       }

C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// 物品结构体（对应Java中的KnapsackItem）
typedef struct {
    int weight;  // 重量
    int value;   // 价值
} KnapsackItem;

// 活结点结构体（对应Java中的ActiveNode）
typedef struct {
    int currentWeight;  // 当前重量
    int currentValue;   // 当前价值
    int nextItemIndex;  // 下一个待处理物品索引
    double upperBound;  // 上界
} ActiveNode;

// 全局数组：存储活结点（模拟Java的PriorityQueue）
ActiveNode* activeNodes;
int nodeCount = 0;  // 活结点数量

// 1. 物品比较函数（按单位价值降序，用于qsort排序）
// 对应Java中的byValuePerWeightDesc比较器
int compareItems(const void* a, const void* b) {
    KnapsackItem* item1 = (KnapsackItem*)a;
    KnapsackItem* item2 = (KnapsackItem*)b;
    // 单位价值比较：item1.value/item1.weight > item2.value/item2.weight
    // 等价于 item1.value * item2.weight > item2.value * item1.weight
    long long val1 = (long long)item1->value * item2->weight;
    long long val2 = (long long)item2->value * item1->weight;
    if (val1 > val2) return -1;  // 降序排列，val1大则item1排前面
    if (val1 < val2) return 1;
    return 0;
}

// 2. 计算上界（限界函数，对应Java的calculateUpperBound）
double calculateUpperBound(int currentWeight, int currentValue, int nextItemIndex,
                          KnapsackItem* sortedItems, int itemCount, int capacity) {
    int remainingCapacity = capacity - currentWeight;
    double upperBound = currentValue;

    if (remainingCapacity <= 0) {
        return upperBound;  // 剩余容量为0，上界即当前价值
    }

    // 按单位价值降序累加后续物品（允许部分装入）
    for (int i = nextItemIndex; i < itemCount; i++) {
        KnapsackItem item = sortedItems[i];
        if (item.weight <= remainingCapacity) {
            upperBound += item.value;
            remainingCapacity -= item.weight;
        } else {
            // 装不下整个物品，按比例计算
            upperBound += (double)remainingCapacity * item.value / item.weight;
            break;  // 后续物品单位价值更低，无需计算
        }
    }
    return upperBound;
}

// 3. 向活结点队列中添加新节点（模拟Java的offer）
void addNode(int currentWeight, int currentValue, int nextItemIndex, double upperBound) {
    // 动态扩容数组（简单实现，实际可优化）
    activeNodes = (ActiveNode*)realloc(activeNodes, (nodeCount + 1) * sizeof(ActiveNode));
    activeNodes[nodeCount].currentWeight = currentWeight;
    activeNodes[nodeCount].currentValue = currentValue;
    activeNodes[nodeCount].nextItemIndex = nextItemIndex;
    activeNodes[nodeCount].upperBound = upperBound;
    nodeCount++;
}

// 4. 从活结点队列中取出上界最大的节点（模拟Java的poll）
ActiveNode getMaxBoundNode() {
    if (nodeCount == 0) {
        ActiveNode empty = {0, 0, 0, 0.0};
        return empty;
    }

    // 找到上界最大的节点索引
    int maxIndex = 0;
    for (int i = 1; i < nodeCount; i++) {
        if (activeNodes[i].upperBound > activeNodes[maxIndex].upperBound) {
            maxIndex = i;
        }
    }

    // 取出该节点
    ActiveNode result = activeNodes[maxIndex];
    // 删除该节点（将最后一个节点移到此处，减少数组操作）
    nodeCount--;
    activeNodes[maxIndex] = activeNodes[nodeCount];
    return result;
}

// 5. 核心算法：分支限界法求解0/1背包
int solveKnapsack(KnapsackItem* originalItems, int itemCount, int capacity) {
    // 步骤1：复制并排序物品（按单位价值降序）
    KnapsackItem* sortedItems = (KnapsackItem*)malloc(itemCount * sizeof(KnapsackItem));
    for (int i = 0; i < itemCount; i++) {
        sortedItems[i] = originalItems[i];
    }
    qsort(sortedItems, itemCount, sizeof(KnapsackItem), compareItems);

    // 步骤2：初始化活结点队列（存储根节点）
    activeNodes = NULL;
    nodeCount = 0;
    double rootUb = calculateUpperBound(0, 0, 0, sortedItems, itemCount, capacity);
    addNode(0, 0, 0, rootUb);

    // 步骤3：初始化最优值
    int maxValue = 0;

    // 步骤4：循环处理活结点
    while (nodeCount > 0) {
        // 取出上界最大的节点
        ActiveNode currentNode = getMaxBoundNode();

        // 剪枝：上界 <= 当前最优值，无需继续处理
        if (currentNode.upperBound <= maxValue) {
            continue;
        }

        // 所有物品处理完毕（叶子节点），更新最优值
        if (currentNode.nextItemIndex == itemCount) {
            if (currentNode.currentValue > maxValue) {
                maxValue = currentNode.currentValue;
            }
            continue;
        }

        // 处理下一个物品（分支：装或不装）
        KnapsackItem nextItem = sortedItems[currentNode.nextItemIndex];
        int nextIndex = currentNode.nextItemIndex + 1;

        // 分支1：装入下一个物品（左分支）
        int newWeight1 = currentNode.currentWeight + nextItem.weight;
        int newValue1 = currentNode.currentValue + nextItem.value;
        if (newWeight1 <= capacity) {  // 不超重
            double ub1 = calculateUpperBound(newWeight1, newValue1, nextIndex, sortedItems, itemCount, capacity);
            if (ub1 > maxValue) {  // 上界大于当前最优值，加入队列
                addNode(newWeight1, newValue1, nextIndex, ub1);
            }
        }

        // 分支2：不装入下一个物品（右分支）
        int newWeight2 = currentNode.currentWeight;
        int newValue2 = currentNode.currentValue;
        double ub2 = calculateUpperBound(newWeight2, newValue2, nextIndex, sortedItems, itemCount, capacity);
        if (ub2 > maxValue) {  // 上界大于当前最优值，加入队列
            addNode(newWeight2, newValue2, nextIndex, ub2);
        }
    }

    // 释放内存
    free(sortedItems);
    free(activeNodes);
    return maxValue;
}

// 主函数：测试指定的0/1背包实例
int main() {
    // 初始化物品（N=3，W=(16,15,15)，P=(45,25,25)）
    KnapsackItem items[] = {
        {16, 45},  // 物品1
        {15, 25},  // 物品2
        {15, 25}   // 物品3
    };
    int itemCount = 3;
    int capacity = 30;  // 背包容量

    // 求解并输出结果
    int optimalValue = solveKnapsack(items, itemCount, capacity);
    printf("0/1背包问题求解结果（N=3）：\n");
    printf("背包容量：%d\n", capacity);
    printf("物品重量：(16, 15, 15)\n");
    printf("物品价值：(45, 25, 25)\n");
    printf("最优解总价值：%d\n", optimalValue);  // 预期输出50
    printf("最优装入方案：不装物品1，装入物品2和物品3（总重量15+15=30）\n");

    return 0;
}