编辑代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1000;

int n = 5;  // 物品的数量
int weight[N] = {6, 5, 4, 2, 1};  // 每个物品的重量
int value[N] = {5, 3, 5, 3, 2};  // 每个物品的价值
int W = 10;  // 背包的容量

int maxValue = 0;  // 最大价值
int bestSelected[N];  // 最优解
// 当前考虑到第i件物品，当前的总重量为w，总价值为v
void backtrack(int i, int w, int v)
{
    // 如果当前的总重量超过背包的容量，直接返回
    if (w > W) return;

    // 如果当前的总价值大于最大价值，更新最大价值和最优解
    if (v > maxValue)
    {
        maxValue = v;
        memcpy(bestSelected, selected, sizeof selected);
    }

    // 如果已经考虑完了所有的物品，返回
    if (i == n) return;

    // 选择第i件物品
    selected[i] = 1;
    backtrack(i+1, w+weight[i], v+value[i]);

    // 不选择第i件物品
    selected[i] = 0;
    backtrack(i+1, w, v);
}

int main()
{
    backtrack(0, 0, 0);

    cout << "最大价值: " << maxValue << endl;
    cout << "选择的物品: ";
    for (int i = 0; i < n; i++)
    {
        if (bestSelected[i])
            cout << i << " ";
    }
    cout << endl;

    return 0;
}