01背包问题回溯法c++

以下是使用回溯法解决01背包问题的C代码：

#include <stdio.h>

#define N 5

int w[N] = {2, 2, 6, 5, 4}; // 物品重量
int v[N] = {6, 3, 5, 4, 6}; // 物品价值
int c = 10; // 背包容量
int x[N] = {0}; // 物品放入情况，0表示不放，1表示放入
int best_x[N] = {0}; // 最优解

int cur_weight = 0; // 当前重量
int cur_value = 0; // 当前总价值
int best_value = 0; // 最优解的总价值

void backtrack(int i)
{
    if (i == N) // 递归结束
    {
        if (cur_value > best_value) // 更新最优解
        {
            best_value = cur_value;
            for (int j = 0; j < N; j++)
            {
                best_x[j] = x[j];
            }
        }
        return;
    }

    // 选择不放第i个物品
    x[i] = 0;
    backtrack(i + 1);

    // 选择放第i个物品
    if (cur_weight + w[i] <= c)
    {
        x[i] = 1;
        cur_weight += w[i];
        cur_value += v[i];
        backtrack(i + 1);
        cur_weight -= w[i];
        cur_value -= v[i];
        x[i] = 0;
    }
}

int main()
{
    backtrack(0);

    printf("最优解：");
    for (int i = 0; i < N; i++)
    {
        printf("%d ", best_x[i]);
    }
    printf("\n最大价值：%d\n", best_value);

    return 0;
}

该代码使用回溯法求解01背包问题，其中：

- `w` 数组存储物品的重量；
- `v` 数组存储物品的价值；
- `c` 表示背包的容量；
- `x` 数组表示物品放入情况，0表示不放，1表示放入；
- `best_x` 数组表示最优解的物品放入情况；
- `cur_weight` 表示当前背包中物品的总重量；
- `cur_value` 表示当前背包中物品的总价值；
- `best_value` 表示最优解的总价值。

在 `backtrack` 函数中，首先选择不放第 `i` 个物品，然后递归进入下一层；然后选择放第 `i` 个物品，如果放入该物品不会超出背包容量，则将该物品放入背包，更新当前重量和总价值，并递归进入下一层；待递归结束后，要回溯到该层，将该物品移出背包，更新当前重量和总价值，并将 `x[i]` 设置为0。