用c语言分支限界法实现01背包问题

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

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

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

// 物品结构体
typedef struct item {
    int id;         // 物品编号
    int weight;     // 物品重量
    int profit;     // 物品价值
    float bound;    // 松弛上界
} item;

// 节点结构体
typedef struct node {
    int level;      // 节点所在层级
    int profit;     // 当前总价值
    int weight;     // 当前总重量
    float bound;    // 松弛上界
} node;

// 全局变量
int n;              // 物品数量
int w;              // 背包容量
item items[MAX_N];  // 物品数组
float max_profit;   // 最大收益
int opt_x[MAX_N];   // 最优解

// 比较函数，用于qsort排序
int cmp(const void *a, const void *b) {
    item *p1 = (item *)a;
    item *p2 = (item *)b;
    float r1 = (float)p1->profit / p1->weight;
    float r2 = (float)p2->profit / p2->weight;
    return r2 > r1 ? 1 : -1;
}

// 计算松弛上界
float get_bound(node n) {
    int level = n.level;
    float bound = n.profit;
    int w = n.weight;
    while (level < n && w < W) {
        if (w + items[level].weight <= W) {
            w += items[level].weight;
            bound += items[level].profit;
        } else {
            float remain = W - w;
            bound += remain * (float)items[level].profit / items[level].weight;
            break;
        }
        level++;
    }
    return bound;
}

// 分支限界法
void branch_bound() {
    node q[MAX_N];   // 队列
    int head = 0, tail = 0;
    node u, v;
    u.level = -1;
    u.profit = u.weight = 0;
    u.bound = get_bound(u);
    q[tail++] = u;
    while (head < tail) {
        u = q[head++];
        if (u.bound > max_profit) {
            v.level = u.level + 1;
            v.weight = u.weight + items[v.level].weight;
            v.profit = u.profit + items[v.level].profit;
            v.bound = get_bound(v);
            if (v.weight <= W && v.profit > max_profit) {
                max_profit = v.profit;
                for (int i = 0; i <= v.level; i++) {
                    opt_x[items[i].id] = items[i].weight;
                }
            }
            if (v.bound > max_profit) {
                q[tail++] = v;
            }
            v.weight = u.weight;
            v.profit = u.profit;
            v.bound = get_bound(v);
            if (v.bound > max_profit) {
                q[tail++] = v;
            }
        }
    }
}

// 主函数
int main() {
    scanf("%d %d", &n, &W);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &items[i].weight, &items[i].profit);
        items[i].id = i;
    }
    qsort(items, n, sizeof(item), cmp);
    branch_bound();
    printf("最大收益为：%f\n", max_profit);
    printf("最优解为：\n");
    for (int i = 0; i < n; i++) {
        printf("%d ", opt_x[i]);
    }
    printf("\n");
    return 0;
}

这个程序实现了01背包问题的分支限界法，使用了一个node结构体表示当前节点的状态，其中包含了当前的层级、总价值、总重量和松弛上界。程序使用了一个队列来保存当前的节点，每次从队列中取出一个节点进行拓展，计算出其子节点的状态，加入队列中。在拓展节点时，如果当前节点的松弛上界大于当前最大收益，则继续拓展，否则直接舍弃。

这个程序的时间复杂度为O(2^n)，因为最坏情况下需要遍历所有可能的节点。