编辑代码

#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 Arr[N][N]; // Arr[i][j]表示前i件物品，重量不超过j的最大价值
int selected[N]; // 记录最优解

int main()
{
// 初始化
memset(Arr, -1, sizeof Arr);
Arr[0][0] = 0;

// 枚举物品数量
for (int i = 1; i <= n; i++)
{
    // 枚举重量
    for (int j = 0; j <= W; j++)
    {
        // 不选择第i件物品
        Arr[i][j] = Arr[i-1][j];

        // 选择第i件物品
        if (j >= weight[i])
            Arr[i][j] = max(Arr[i][j], Arr[i-1][j-weight[i]]+value[i]);
    }
}

cout << "最大价值: " << Arr[n][W] << endl;

// 构造最优解
int i = n, j = W;
while (i > 0 && j > 0)
{
    if (Arr[i][j] == Arr[i-1][j])
    {
        // 不选择第i件物品
        selected[i] = 0;
    }
    else
    {
        // 选择第i件物品
        selected[i] = 1;
        j -= weight[i];
    }
    i--;
}

cout << "选择的物品(从0开始数): ";
for (int i = 1; i < n; i++)
{
    if (selected[i]) cout << i << " ";
}
cout << endl;

return 0;
}