采用回溯法求解0/1背包问题用C语言实现

下面是一个使用回溯法求解0/1背包问题的C语言实现：

#include <stdio.h>

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

int w[N] = {2, 2, 6, 5, 4};  // 物品重量
int v[N] = {6, 3, 5, 4, 6};  // 物品价值
int x[N];                    // 最优解
int maxValue = 0;            // 最大价值

void backtrack(int i, int cw, int cv) {
    if (i == N) {  // 达到叶子节点
        if (cv > maxValue) {   // 更新最大价值
            maxValue = cv;
            for (int j = 0; j < N; j++) {
                x[j] = w[j];
            }
        }
        return;
    }

    // 不选择第i个物品
    backtrack(i + 1, cw, cv);

    // 选择第i个物品
    if (cw + w[i] <= C) {   // 可行性剪枝
        x[i] = 1;
        backtrack(i + 1, cw + w[i], cv + v[i]);
        x[i] = 0;
    }
}

int main() {
    backtrack(0, 0, 0);   // 从根节点开始搜索
    printf("maxValue = %d\n", maxValue);
    printf("x = [");
    for (int i = 0; i < N; i++) {
        printf("%d ", x[i]);
    }
    printf("]\n");
    return 0;
}

该程序定义了物品的重量和价值数组 `w` 和 `v`，以及最优解数组 `x` 和最大价值 `maxValue`。在 `backtrack` 函数中，使用回溯法搜索所有的可能性，如果达到叶子节点，就更新最大价值和最优解。在搜索过程中，使用可行性剪枝来提高效率。

在主函数中，调用 `backtrack` 函数开始搜索，最后输出最大价值和最优解。