分支限界法用C语言求解0/1背包问题

以下是使用分支限界法用C语言求解0/1背包问题的代码示例：

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

#define MAX_N 1000

typedef struct {
    int v; // 物品价值
    int w; // 物品重量
    double p; // 物品单位价值
} Item;

typedef struct {
    int level; // 当前搜索的层数
    int profit; // 当前已获得的价值
    int weight; // 当前已获得的重量
    double bound; // 当前结点的价值上界
} Node;

int n; // 物品数量
int c; // 背包容量
Item items[MAX_N]; // 物品数组
Node queue[MAX_N]; // 结点队列
int front, rear; // 队列头尾指针

// 比较函数，用于优先队列的排序
int cmp(const void *a, const void *b) {
    Node *pa = (Node *)a;
    Node *pb = (Node *)b;
    return pb->bound - pa->bound;
}

// 计算结点的价值上界
double bound(Node node) {
    if (node.weight >= c) {
        return 0;
    }
    double profit_bound = node.profit;
    int j = node.level + 1;
    int tot_weight = node.weight;
    while (j <= n && tot_weight + items[j].w <= c) {
        tot_weight += items[j].w;
        profit_bound += items[j].v;
        j++;
    }
    if (j <= n) {
        profit_bound += (c - tot_weight) * items[j].p;
    }
    return profit_bound;
}

// 分支限界法求解0/1背包问题
int knapsack() {
    // 初始化队列
    Node root = {0, 0, 0, bound((Node){0, 0, 0, 0})};
    queue[0] = root;
    front = 0;
    rear = 1;

    int max_profit = 0;
    while (front < rear) {
        // 取出队首结点
        Node node = queue[front];
        front++;

        // 如果当前结点的价值上界小于已知的最大价值，则剪枝
        if (node.bound <= max_profit) {
            continue;
        }

        // 如果当前结点是叶子结点，则更新最大价值
        if (node.level == n) {
            max_profit = node.profit;
            continue;
        }

        // 扩展结点
        Node left = {node.level + 1, node.profit + items[node.level + 1].v, node.weight + items[node.level + 1].w, bound((Node){node.level + 1, node.profit + items[node.level + 1].v, node.weight + items[node.level + 1].w, 0})};
        Node right = {node.level + 1, node.profit, node.weight, bound((Node){node.level + 1, node.profit, node.weight, 0})};
        if (left.weight <= c) {
            queue[rear] = left;
            rear++;
        }
        queue[rear] = right;
        rear++;

        // 对队列按照价值上界从大到小排序
        qsort(queue + front, rear - front, sizeof(Node), cmp);
    }

    return max_profit;
}

int main() {
    // 读入物品数量和背包容量
    scanf("%d%d", &n, &c);

    // 读入物品信息
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &items[i].v, &items[i].w);
        items[i].p = (double)items[i].v / items[i].w;
    }

    // 求解0/1背包问题
    int max_profit = knapsack();

    // 输出结果
    printf("%d\n", max_profit);

    return 0;
}