用回溯法写背包问题c代码

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

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

#define MAX_N 1000

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 calc_v() {
    int res = 0;
    for (int i = 0; i < n; i++) {
        if (x[i]) {
            res += v[i];
        }
    }
    return res;
}

// 回溯搜索
void backtrack(int i) {
    if (i == n) { // 达到叶子节点
        if (cur_v > best_v) { // 更新最优解
            best_v = cur_v;
            for (int j = 0; 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];
    }
    x[i] = 0; // 不选择第i个物品放入背包
    backtrack(i + 1);
}

int main() {
    scanf("%d%d", &n, &c);
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &w[i], &v[i]);
    }
    backtrack(0);
    printf("%d\n", best_v);
    return 0;
}