编辑代码

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

#define MAX_ITEMS 100

// 物品结构体定义
typedef struct {
    int weight;
    int value;
} Item;

// 节点结构体定义
typedef struct {
    int level;       // 节点所在层次
    int profit;      // 节点处的价值
    int weight;      // 节点处的重量
    double bound;    // 节点处的价值上界
} Node;

// 用于优先队列的比较函数
int compareNodes(const void *a, const void *b) {
    return ((Node *)a)->bound - ((Node *)b)->bound;
}

// 计算节点的价值上界
double calculateBound(Node node, int numItems, int capacity, Item items[]) {
    int j, k;
    double bound = node.profit;
    int totalWeight = node.weight;

    if (node.weight >= capacity) {
        return 0;
    }

    for (j = node.level + 1; j < numItems; j++) {
        if (totalWeight + items[j].weight <= capacity) {
            bound += items[j].value;
            totalWeight += items[j].weight;
        } else {
            k = j;
            break;
        }
    }

    if (k < numItems) {
        bound += (capacity - totalWeight) * items[k].value / (double)items[k].weight;
    }

    return bound;
}

// 分支界限法解决背包问题
int branchAndBound(Item items[], int numItems, int capacity) {
    Node *priorityQueue = (Node *)malloc(sizeof(Node) * MAX_ITEMS * 2);
    int queueSize = 0;

    // 根节点
    Node root = {0, 0, 0, 0};
    root.bound = calculateBound(root, numItems, capacity, items);

    // 将根节点加入优先队列
    priorityQueue[queueSize++] = root;

    int maxProfit = 0;

    while (queueSize > 0) {
        // 从队列中取出最高优先级的节点
        Node currentNode = priorityQueue[--queueSize];

        // 如果当前节点的上界小于当前已知的最优解，则剪枝
        if (currentNode.bound > maxProfit) {
            // 左子节点：选择放入当前物品
            Node leftChild = {currentNode.level + 1,
                              currentNode.profit + items[currentNode.level + 1].value,
                              currentNode.weight + items[currentNode.level + 1].weight,
                              0};
            leftChild.bound = calculateBound(leftChild, numItems, capacity, items);

            // 如果左子节点是可行节点，更新最优解
            if (leftChild.weight <= capacity && leftChild.profit > maxProfit) {
                maxProfit = leftChild.profit;
            }

            // 将左子节点加入优先队列
            if (leftChild.bound > maxProfit) {
                priorityQueue[queueSize++] = leftChild;
            }

            // 右子节点：选择不放入当前物品
            Node rightChild = {currentNode.level + 1,
                               currentNode.profit,
                               currentNode.weight,
                               0};
            rightChild.bound = calculateBound(rightChild, numItems, capacity, items);

            // 如果右子节点是可行节点，更新最优解
            if (rightChild.weight <= capacity && rightChild.profit > maxProfit) {
                maxProfit = rightChild.profit;
            }

            // 将右子节点加入优先队列
            if (rightChild.bound > maxProfit) {
                priorityQueue[queueSize++] = rightChild;
            }
        }
    }

    free(priorityQueue);

    return maxProfit;
}

int main() {
    Item items[] = {{2, 5}, {3, 8}, {5, 12}};
    int numItems = sizeof(items) / sizeof(items[0]);
    int capacity = 5;

    int result = branchAndBound(items, numItems, capacity);

    printf("最大总价值: %d\n", result);

    return 0;
}