分支限界法 01背包c语言,算法笔记分支限界法01背包问题 输出最优值和最优解 代码要有注释

好的，下面是使用分支限界法解决01背包问题的C语言代码，包含注释：

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

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

int n, W; // 物品数量、背包容量
int w[MAX_N], v[MAX_N]; // 物品的重量、价值
int max_v = 0, max_x[MAX_N]; // 最优解的价值、每个物品选择的情况

// 计算上界，以价值为下界，剩余物品按单位价值从大到小装满背包
double upper_bound(int i, int cur_w, int cur_v) {
    double bound = cur_v;
    int j;
    for (j = i; j < n && cur_w + w[j] <= W; j++) {
        bound += v[j];
        cur_w += w[j];
    }
    if (j < n) {
        bound += (W - cur_w) * 1.0 * v[j] / w[j];
    }
    return bound;
}

// 搜索函数
void dfs(int i, int cur_w, int cur_v, int x[]) {
    if (i == n) { // 到达叶子节点，更新最优解
        if (cur_v > max_v) {
            max_v = cur_v;
            int j;
            for (j = 0; j < n; j++) {
                max_x[j] = x[j];
            }
        }
        return;
    }
    if (cur_w + w[i] <= W) { // 左子树：选择第i个物品
        x[i] = 1;
        dfs(i + 1, cur_w + w[i], cur_v + v[i], x);
        x[i] = 0;
    }
    if (upper_bound(i + 1, cur_w, cur_v) > max_v) { // 右子树：不选第i个物品
        dfs(i + 1, cur_w, cur_v, x);
    }
}

int main() {
    // 读入数据
    scanf("%d%d", &n, &W);
    int i;
    for (i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }

    // 初始化最优解
    for (i = 0; i < n; i++) {
        max_x[i] = 0;
    }

    // 搜索
    int x[MAX_N]; // 当前搜索到的解
    dfs(0, 0, 0, x);

    // 输出最优解
    printf("最优值：%d\n", max_v);
    printf("最优解：");
    for (i = 0; i < n; i++) {
        printf("%d ", max_x[i]);
    }
    printf("\n");

    return 0;
}

代码中使用了dfs函数进行搜索，upper_bound函数计算上界，max_x数组记录最优解的每个物品选择情况。注释详细解释了每个函数的作用和实现方式。