背包问题回溯法C语言实现

背包问题是一个经典的问题，它的目标是在一组物品中选择最有价值的物品放入一个背包中，使得背包能够承受的重量不超过给定的限制，同时价值最大化。下面是使用回溯法实现背包问题的C语言代码：

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

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

int w[] = {2, 2, 6, 5, 4};   // 物品的重量
int v[] = {6, 3, 5, 4, 6};   // 物品的价值
int x[N] = {0};              // 当前解
int bestx[N] = {0};          // 最优解
int cw = 0;                  // 当前背包重量
int bestv = 0;               // 最优价值

// 回溯法求背包问题
void backtrack(int i)
{
    if (i >= N)
    {
        if (bestv < cw)
        {
            bestv = cw;
            for (int j = 0; j < N; j++)
                bestx[j] = x[j];
        }
        return;
    }

    if (cw + w[i] <= C)
    {
        x[i] = 1;           // 把物品i放入背包中
        cw += w[i];
        backtrack(i + 1);
        cw -= w[i];
    }

    x[i] = 0;               // 不把物品i放入背包中
    backtrack(i + 1);
}

int main()
{
    backtrack(0);

    printf("最优价值为：%d\n", bestv);
    printf("最优解为：");
    for (int i = 0; i < N; i++)
        printf("%d ", bestx[i]);
    printf("\n");

    return 0;
}

在该代码中，`w`和`v`数组分别存储了物品的重量和价值，`x`数组用于记录当前解，`bestx`数组用于存储最优解，`cw`变量表示当前背包重量，`bestv`变量表示最优价值。`backtrack`函数是回溯函数，它从第0个物品开始递归搜索所有可能的解，并在搜索过程中更新最优解。在搜索过程中，如果将第`i`个物品放入背包中，就将`x[i]`设置为1，并将背包重量`cw`增加`w[i]`；如果不将第`i`个物品放入背包中，就将`x[i]`设置为0。最后，输出最优价值和最优解即可。