递归回溯法求解0/1背包问题C语言完整代码

下面是使用递归回溯法求解0/1背包问题的C语言完整代码：

#include <stdio.h>
#define N 5  // 物品数量
#define W 10  // 背包容量

int w[N] = {2, 5, 4, 2, 3};  // 物品重量列表
int p[N] = {6, 3, 5, 4, 6};  // 物品价值列表

int max(int a, int b) {
    return (a > b) ? a : b;
}

int knapsack(int i, int j) {
    if (i == 0 || j == 0) {
        return 0;
    }
    if (w[i-1] > j) {
        return knapsack(i-1, j);
    }
    else {
        return max(knapsack(i-1, j), p[i-1] + knapsack(i-1, j-w[i-1]));
    }
}

int main() {
    int max_profit = knapsack(N, W);
    printf("最大总价值为：%d\n", max_profit);
    return 0;
}

其中，`knapsack`函数是递归回溯函数，`i`表示当前选到第几个物品，`j`表示当前背包容量。当`i`或`j`等于0时，返回0。如果第`i`个物品的重量大于当前背包容量`j`，则不能选第`i`个物品，继续考虑选前`i-1`个物品的最优解，即递归调用`knapsack(i-1, j)`。否则，考虑选或不选第`i`个物品，取两者之间的最大值，即`max(knapsack(i-1, j), p[i-1] + knapsack(i-1, j-w[i-1]))`。在程序最后，输出最大总价值。