01背包问题分支限界算法（C语言实现）

好的，以下是01背包问题的分支限界算法的C语言实现：

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

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

int n, W; // 物品数量和背包容量
int v[MAX_N], w[MAX_N]; // 物品的价值和重量
int max_v = 0; // 最大价值
int best[MAX_N]; // 最优解

typedef struct Node {
    int level; // 当前节点所在层数
    int value; // 当前价值
    int weight; // 当前重量
    int bound; // 当前上界
} Node;

Node q[MAX_N]; // 优先队列
int head = 0, tail = 0; // 队列头和尾

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

// 计算节点的上界
int calc_bound(Node node) {
    int value = node.value;
    int weight = node.weight;
    int level = node.level;
    while (level < n && weight + w[level] <= W) {
        value += v[level];
        weight += w[level];
        level++;
    }
    if (level < n) {
        value += (W - weight) * v[level] / w[level];
    }
    return value;
}

// 分支限界算法
void branch_and_bound() {
    Node u, v;
    u.level = 0;
    u.value = 0;
    u.weight = 0;
    u.bound = calc_bound(u);
    q[tail++] = u;
    while (head != tail) {
        u = q[head++];
        if (u.bound > max_v) {
            v.level = u.level + 1;
            v.value = u.value + v[u.level];
            v.weight = u.weight + w[u.level];
            if (v.weight <= W && v.value > max_v) {
                max_v = v.value;
                for (int i = 0; i < v.level; i++) {
                    best[i] = 0;
                }
                best[v.level - 1] = 1;
            }
            v.bound = calc_bound(v);
            if (v.bound > max_v) {
                q[tail++] = v;
            }
            v.value = u.value;
            v.weight = u.weight;
            v.bound = calc_bound(v);
            if (v.bound > max_v) {
                q[tail++] = v;
            }
        }
    }
}

int main() {
    printf("请输入物品数量和背包容量：");
    scanf("%d%d", &n, &W);
    printf("请输入每个物品的价值和重量：\n");
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &v[i], &w[i]);
    }
    branch_and_bound();
    printf("最大价值为：%d\n", max_v);
    printf("最优解为：\n");
    for (int i = 0; i < n; i++) {
        if (best[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

该算法的时间复杂度为 $O(2^n)$，但由于使用了优先队列，实际运行时间会比较快。