如何在动态规划求解的0-1背包问题中确定选中物品？

我用动态规划实现了0-1背包问题，输入背包最大承重60时，程序能输出最大价值15，但我还需要打印出被选中的物品（比如输出15后，依次显示platinum、gold、silver）。我尝试在item结构体中添加calltime字段，通过增减该值标记选中物品，但这个方法无效，求可行的实现方案。

现有代码 #

#include <iostream>
using namespace std;
#define number 4 // number of item type

typedef struct iteml
{
    int itemw; // [weight of item]
    int itemv; // [value of item]
    char name[30]; // [name of item]
}iteml;

int main()
{
    int item_number = number; // number of item type
    int backpack_weight; //maximum weigth of backpack

    iteml item[number+1]; // [number of item type +1]
    item[1] = { 10, 6, "platinum" };
    item[2] = { 15, 5, "gold" };
    item[3] = { 25, 4, "silver" };
    item[4] = { 50, 1, "steel" };

    int dp[number+1][61] = { 0, }; // [number of item type +1] [maximum weigth of backpack]
    int i, w = 1;

    cout << "type maximum weigth of backpack. : ";
    cin >> backpack_weight;

    for (i = 1; i <= item_number; i++)
    {
        for (w = 1; w <= backpack_weight; w++)
        {
            if (item[i].itemw<= w)
            { 
                if ((item[i].itemv + dp[i - 1][w - item[i].itemw]) > dp[i - 1][w])
                {
                    dp[i][w] = item[i].itemv + dp[i - 1][w - item[i].itemw];
                }
                else
                {
                    dp[i][w] = dp[i - 1][w];
                }
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    printf("%d", dp[item_number][backpack_weight]);
    return 0;
}

输入输出示例 #

• 输入：

60

• 输出：

15

无效尝试 #

我曾修改结构体添加calltime字段，但无法通过该字段确定选中物品：

typedef struct iteml
{
    int itemw; // [weight of item]
    int itemv; // [value of item]
    int calltime; 
    char name[30]; // [name of item]
}iteml;

解决方案：通过DP表回溯确定选中物品 #

不需要修改item结构体，核心思路是利用已生成的DP表反向回溯，判断每个物品是否被选中：

1. 从DP表的最后一个状态（i = item_number, w = backpack_weight）开始
2. 比较dp[i][w]和dp[i-1][w]：
   • 如果两者不相等，说明第i个物品被选中，记录该物品名称，然后将背包剩余重量w减去该物品的重量，同时i减1
   • 如果两者相等，说明第i个物品未被选中，直接将i减1
3. 重复步骤2，直到i减至0为止

修改后的完整代码 #

#include <iostream>
using namespace std;
#define number 4 // number of item type

typedef struct iteml
{
    int itemw; // [weight of item]
    int itemv; // [value of item]
    char name[30]; // [name of item]
}iteml;

int main()
{
    int item_number = number; // number of item type
    int backpack_weight; //maximum weigth of backpack

    iteml item[number+1]; // [number of item type +1]
    item[1] = { 10, 6, "platinum" };
    item[2] = { 15, 5, "gold" };
    item[3] = { 25, 4, "silver" };
    item[4] = { 50, 1, "steel" };

    int dp[number+1][61] = { 0, }; // [number of item type +1] [maximum weigth of backpack]
    int i, w = 1;

    cout << "type maximum weigth of backpack. : ";
    cin >> backpack_weight;

    // 动态规划填充DP表
    for (i = 1; i <= item_number; i++)
    {
        for (w = 1; w <= backpack_weight; w++)
        {
            if (item[i].itemw <= w)
            { 
                if ((item[i].itemv + dp[i - 1][w - item[i].itemw]) > dp[i - 1][w])
                {
                    dp[i][w] = item[i].itemv + dp[i - 1][w - item[i].itemw];
                }
                else
                {
                    dp[i][w] = dp[i - 1][w];
                }
            }
            else
            {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    // 输出最大价值
    printf("最大价值：%d\n", dp[item_number][backpack_weight]);

    // 回溯找出选中的物品
    printf("选中的物品：\n");
    i = item_number;
    w = backpack_weight;
    while (i > 0 && w > 0)
    {
        if (dp[i][w] != dp[i-1][w])
        {
            // 第i个物品被选中
            printf("- %s\n", item[i].name);
            w -= item[i].itemw;
        }
        i--;
    }

    return 0;
}

代码说明 #

• 回溯逻辑中，dp[i][w] != dp[i-1][w]意味着加入第i个物品后总价值更高，因此该物品被选中
• 每次选中物品后，需要将背包剩余重量减去该物品的重量，继续回溯前面的物品
• 最终输出的物品顺序是从最后一个选中的到第一个，若需要正序，可将选中的物品存入数组后反向输出

内容的提问来源于stack exchange，提问作者RyuJin