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

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

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 20 //物品数量最大值
#define MAX_W 100 //背包容量最大值

int n, W; //物品数量、背包容量
int w[MAX_N], v[MAX_N]; //物品重量、价值
int best_v; //最优解的价值
int cur_w, cur_v; //当前解的重量、价值
int used[MAX_N]; //当前解中物品是否已选标记数组

//回溯函数
void backtrack(int t)
{
    if (t > n)
    {
        if (cur_v > best_v)
            best_v = cur_v;
        return;
    }
    //不选第t个物品
    used[t] = 0;
    backtrack(t + 1);
    //选第t个物品
    if (cur_w + w[t] <= W)
    {
        used[t] = 1;
        cur_w += w[t];
        cur_v += v[t];
        backtrack(t + 1);
        cur_w -= w[t];
        cur_v -= v[t];
        used[t] = 0;
    }
}

int main()
{
    printf("请输入物品数量和背包容量：\n");
    scanf("%d%d", &n, &W);
    printf("请输入每个物品的重量和价值：\n");
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &w[i], &v[i]);
    best_v = 0;
    cur_w = cur_v = 0;
    backtrack(1);
    printf("最优解的价值为：%d\n", best_v);
    return 0;
}

该程序采用了递归回溯的思想，通过枚举所有可能的选择方案，得到最优解的价值。其中，used数组用于标记当前解中哪些物品已经选中，cur_w和cur_v分别表示当前解的重量和价值。在每次递归时，先尝试不选第t个物品，然后再尝试选第t个物品。如果选了第t个物品，就要更新当前解的重量和价值，并将used数组中第t个位置标记为1，表示该物品已选中。当t>n时，说明已经枚举完了所有物品，此时如果当前解的价值比最优解的价值更大，就更新最优解的价值。