背包问题c语言回溯法

#include <stdio.h>

#define N 5  // 物品的数量
#define C 10 // 背包的容量

int maxV = 0; // 最大价值
int weight[N] = {2, 2, 6, 5, 4}; // 每个物品的重量
int value[N] = {6, 3, 5, 4, 6};  // 每个物品的价值
int x[N] = {0}; // 存放最终解

void backtrack(int t, int curW, int curV) {
    if (t > N - 1) {  // 到达叶节点
        if (curV > maxV) {
            maxV = curV;
            for (int i = 0; i < N; i++) {
                x[i] = weight[i];
            }
        }
        return;
    }
    if (curW + weight[t] <= C) {  // 左子树
        curW += weight[t];
        curV += value[t];
        backtrack(t + 1, curW, curV);
        curW -= weight[t];
        curV -= value[t];
    }
    backtrack(t + 1, curW, curV);  // 右子树
}

int main() {
    backtrack(0, 0, 0);
    printf("背包中物品的总价值最大为：%d\n", maxV);
    printf("放入背包的物品重量分别为：");
    for (int i = 0; i < N; i++) {
        if (x[i] != 0) {
            printf("%d ", x[i]);
        }
    }
    return 0;
}