回溯法解决01背包问题C语言

以下是使用回溯法解决01背包问题的C语言代码：

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

#define MAX_N 100

int n, c; // 物品数量和背包容量
int w[MAX_N], v[MAX_N]; // 物品的重量和价值
int cur_w, cur_v; // 当前背包中物品的重量和价值
int best_v; // 最优解的价值
int x[MAX_N], best_x[MAX_N]; // 当前解和最优解

// 计算上界函数
int bound(int i) {
    int b = cur_v;
    int c_left = c - cur_w; // 剩余容量
    while (i <= n && w[i] <= c_left) {
        c_left -= w[i];
        b += v[i];
        i++;
    }
    if (i <= n) {
        b += v[i] * c_left / w[i];
    }
    return b;
}

// 回溯搜索
void backtrack(int i) {
    if (i > n) {
        if (cur_v > best_v) {
            best_v = cur_v;
            for (int j = 1; j <= n; j++) {
                best_x[j] = x[j];
            }
        }
        return;
    }
    if (cur_w + w[i] <= c) { // 选择第i个物品
        x[i] = 1;
        cur_w += w[i];
        cur_v += v[i];
        backtrack(i + 1);
        cur_w -= w[i];
        cur_v -= v[i];
    }
    if (bound(i + 1) > best_v) { // 不选择第i个物品
        x[i] = 0;
        backtrack(i + 1);
    }
}

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