分支限界法解决01背包用C语言编写代码

以下是使用分支限界法解决01背包问题的C语言代码：

#include <stdio.h>

#define MAX_N 100 // 最大物品数量
#define MAX_W 1000 // 最大背包容量

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

typedef struct {
    int level; // 当前搜索的深度
    int profit; // 当前收益
    int weight; // 当前重量
} Node;

Item items[MAX_N]; // 存储物品信息
int n, max_w; // 物品数量和背包容量
int max_profit = 0; // 最大收益

void knapsack() {
    Node q[MAX_N * MAX_W]; // 存储搜索状态的队列
    int head = 0, tail = 0; // 队列头尾指针
    Node u, v; // 当前搜索状态和下一状态
    u.level = -1; // 初始状态为根节点，深度为-1
    u.profit = u.weight = 0;
    q[tail++] = u;
    while (head != tail) { // 队列不为空时循环
        u = q[head++]; // 取出队首搜索状态
        if (u.level == n - 1) { // 叶节点，更新最大收益
            if (u.profit > max_profit) {
                max_profit = u.profit;
            }
            continue;
        }
        v.level = u.level + 1; // 扩展下一状态
        v.weight = u.weight + items[v.level].w;
        v.profit = u.profit + items[v.level].v;
        if (v.weight <= max_w && v.profit > max_profit) { // 更新最大收益
            max_profit = v.profit;
        }
        if (bound(v) > max_profit) { // 如果可行，则加入队列
            q[tail++] = v;
        }
        v.weight = u.weight; // 不选当前物品的状态
        v.profit = u.profit;
        if (bound(v) > max_profit) { // 如果可行，则加入队列
            q[tail++] = v;
        }
    }
}

int bound(Node u) {
    if (u.weight >= max_w) { // 超过背包容量，不可行
        return 0;
    }
    int profit_bound = u.profit;
    int i;
    for (i = u.level + 1; i < n && u.weight + items[i].w <= max_w; i++) {
        u.weight += items[i].w;
        profit_bound += items[i].v;
    }
    if (i < n) { // 无法装满背包，计算部分装入的收益
        profit_bound += (max_w - u.weight) * items[i].v / items[i].w;
    }
    return profit_bound;
}

int main() {
    scanf("%d %d", &n, &max_w);
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d %d", &items[i].w, &items[i].v);
    }
    knapsack();
    printf("%d\n", max_profit);
    return 0;
}

该算法的时间复杂度为$O(2^n)$，在物品数量较大时会极大地影响效率，因此分支限界法适用于物品数量较小的情况。