编辑代码

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

#define N 100
//结构体
typedef struct {
    int level;      
    int profit;     
    int weight;     
    float bound;    
} Node;

typedef struct {
    int index;        // 物品的索引
    float bound;      // 物品的上界
} QueueElement;

// 比较函数，用于优先队列的排序
int compare(const void *a, const void *b) {
    float diff = ((QueueElement *)a)->bound - ((QueueElement *)b)->bound;
    return (diff > 0) ? 1 : ((diff < 0) ? -1 : 0);
}

// 最小堆的向上调整
void heapifyUp(QueueElement *queue, int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (queue[index].bound < queue[parent].bound) {
            // 交换元素
            QueueElement temp = queue[index];
            queue[index] = queue[parent];
            queue[parent] = temp;
            index = parent;
        } else {
            break;
        }
    }
}

// 分支限界法解决背包问题
int knapsackBranchBound(int values[], int weights[], int n, int capacity) {
    Node root = { .level = -1, .profit = 0, .weight = 0, .bound = 0 };
    int maxProfit = 0;

    // 初始化最小堆
    QueueElement *queue = (QueueElement *)malloc(sizeof(QueueElement) * n);
    int rear = -1;

    // 将根节点加入最小堆
    queue[++rear] = (QueueElement){ .index = -1, .bound = root.bound };

    while (rear != -1) {
        QueueElement current = queue[0];  // 获取当前最小的上界节点
        rear--;

        // 从最小堆删除当前节点
        queue[0] = queue[rear + 1];

        // 最小堆的向下调整
        int index = 0;
        while (1) {
            int leftChild = 2 * index + 1;
            int rightChild = 2 * index + 2;
            int minIndex = index;

            if (leftChild <= rear && queue[leftChild].bound < queue[minIndex].bound) {
                minIndex = leftChild;
            }

            if (rightChild <= rear && queue[rightChild].bound < queue[minIndex].bound) {
                minIndex = rightChild;
            }

            if (minIndex != index) {
                // 交换元素
                QueueElement temp = queue[index];
                queue[index] = queue[minIndex];
                queue[minIndex] = temp;
                index = minIndex;
            } else {
                break;
            }
        }

        int i = current.index + 1;
        Node next;
        next.level = root.level + 1;
        next.weight = root.weight + weights[i];
        next.profit = root.profit + values[i];

        // 如果选择当前物品不超过容量，更新最大价值
        if (next.weight <= capacity && next.profit > maxProfit) {
            maxProfit = next.profit;
        }

        next.bound = (float)next.profit + (float)(capacity - next.weight) * values[i] / weights[i];

        // 如果上界大于当前最大价值，将左子树加入最小堆
        if (next.bound > maxProfit && next.level < n - 1) {
            queue[++rear] = (QueueElement){ .index = i, .bound = next.bound };
            heapifyUp(queue, rear);  // 最小堆的向上调整
        }

        // 不选择当前物品，计算右子树的上界
        next.weight = root.weight;
        next.profit = root.profit;
        next.bound = (float)next.profit + (float)(capacity - next.weight) * values[i] / weights[i];

        // 如果上界大于当前最大价值，将右子树加入最小堆
        if (next.bound > maxProfit && next.level < n - 1) {
            queue[++rear] = (QueueElement){ .index = i, .bound = next.bound };
            heapifyUp(queue, rear);  // 最小堆的向上调整
        }
    }

    free(queue);

    return N;
}

int main() {
    int values[] = {60, 100, 120};
    int weights[] = {10, 20, 30};
    int n = sizeof(values) / sizeof(values[0]);
    int capacity = 50;

    int result = knapsackBranchBound(values, weights, n, capacity);

    printf("最大值 = %d\n", result);

    return 0;
}