01背包问题回溯法c语言

下面是C语言的01背包问题回溯法代码实现：

#include <stdio.h>
#define MAX_N 100
#define MAX_W 1000
 
int n, W;
int w[MAX_N], v[MAX_N];
int max_value = 0;
int cur_weight = 0, cur_value = 0;
 
void dfs(int i)
{
    if (i == n) {
        if (cur_weight <= W && cur_value > max_value)
            max_value = cur_value;
        return;
    }
 
    // 不选第i个物品
    dfs(i + 1);
 
    // 选第i个物品
    cur_weight += w[i];
    cur_value += v[i];
    dfs(i + 1);
    cur_weight -= w[i];
    cur_value -= v[i];
}
 
int main()
{
    scanf("%d%d", &n, &W);
    for (int i = 0; i < n; ++i)
        scanf("%d%d", &w[i], &v[i]);
 
    dfs(0);
 
    printf("%d\n", max_value);
    return 0;
}

程序首先输入物品数量n和背包容量W，然后依次输入每个物品的重量和价值。接下来，程序调用dfs函数进行搜索。dfs函数的参数i表示当前正在考虑第i个物品。如果i等于n，说明所有物品都已经考虑过了，此时判断是否满足背包容量的限制，并更新最大价值。

在dfs函数中，首先不选第i个物品，然后递归调用dfs函数，考虑下一个物品。接着，选第i个物品，更新当前重量和价值，并递归调用dfs函数，考虑下一个物品。最后，回溯到上一个状态，将当前重量和价值恢复到之前的值。

程序结束后，输出最大价值即可。