0-1背包问题的回溯算法C语言

以下是0-1背包问题的回溯算法C语言实现：

#include <stdio.h>
#define MAX 100

int weight[MAX], value[MAX];
int max_weight, max_value, n;

void backtrack(int i, int tw, int tv) {
    if (i > n) {
        if (tw <= max_weight && tv > max_value) {
            max_value = tv;
        }
        return;
    }
    backtrack(i + 1, tw, tv);
    if (tw + weight[i] <= max_weight) {
        backtrack(i + 1, tw + weight[i], tv + value[i]);
    }
}

int main() {
    printf("请输入物品数量和背包容量：\n");
    scanf("%d %d", &n, &max_weight);
    printf("请输入物品的重量和价值：\n");
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &weight[i], &value[i]);
    }
    backtrack(1, 0, 0);
    printf("可以放入背包的最大价值为：%d\n", max_value);
    return 0;
}

其中，`weight`和`value`数组分别存储了物品的重量和价值，`max_weight`为背包的容量，`max_value`为可以放入背包的最大价值，`n`为物品数量。`backtrack`函数用于进行回溯，参数`i`表示当前考虑的物品编号，`tw`表示当前背包中物品的重量，`tv`表示当前背包中物品的价值。在回溯过程中，如果当前考虑的物品编号超过了物品数量，就判断当前的背包中物品是否满足要求，并更新最大价值。否则，可以选择不放入当前物品，或者放入当前物品，然后进行下一轮回溯。在放入当前物品时，需要判断是否超过了背包的容量。