无界背包最优解路径求解：如何获取各物品选取数量n_k？

嗨，很高兴你已经搞定了无界背包变体的最优价值计算！要拿到每个物品的选取数量n_k，只需要在动态规划的过程中多维护一个追踪数组，记录每个状态下的选择，最后回溯就能得到结果啦。下面是具体的实现步骤和C++代码示例：

核心思路是在DP过程中记录每一步的选择，之后通过回溯从最终状态倒推回去，统计每个物品的使用次数。

1. 新增追踪数组 #

除了原来的DP数组（比如dp[w]表示总重量不超过w时的最大价值），我们需要一个额外的数组，比如choice[w]，它的作用是：记录当达到dp[w]这个最优价值时，最后添加的物品是哪一个（物品的索引k）。

初始化时，choice数组可以设为-1（表示该重量下没有选择任何物品），dp数组初始为0。

2. 修改DP状态转移逻辑 #

在更新DP数组的同时，同步更新choice数组。当发现选择物品k可以让当前重量w的价值更大时，就记录下这个物品k：

// 假设weight[]是物品的重量数组，value[]是物品的价值数组，num_items是物品总数
vector<int> dp(W_max + 1, 0);
vector<int> choice(W_max + 1, -1);

for (int w = 1; w <= W_max; ++w) {
    for (int k = 0; k < num_items; ++k) {
        // 确保当前重量能放下物品k，且选择它能得到更大的价值
        if (w >= weight[k] && dp[w - weight[k]] + value[k] > dp[w]) {
            dp[w] = dp[w - weight[k]] + value[k];
            choice[w] = k; // 记录选择的物品k
        }
    }
}

3. 回溯获取n_k #

从最终的状态（也就是重量W_max，因为dp[W_max]是约束下的最大价值）开始倒推，每次取出choice[current_w]得到最后选择的物品k，将该物品的计数加1，然后把当前重量减去物品k的重量，重复这个过程直到当前重量为0或者choice[current_w]为-1：

vector<int> n(num_items, 0);
int current_w = W_max;

while (current_w > 0 && choice[current_w] != -1) {
    int k = choice[current_w];
    n[k]++; // 物品k的数量加1
    current_w -= weight[k]; // 减去该物品的重量，回到上一个状态
}

此时，n数组中的每个元素n[k]就是对应物品k的最优选取数量啦。

注意事项 #

• 如果存在多个最优解（不同的n_k组合能得到相同的最大价值），这个方法会得到其中一个可行的最优解。如果需要所有最优解，那就要更复杂的记录方式，但通常单个最优解就足够了。
• 如果你实际的问题是约束和目标反过来（比如约束总价值≤W_max，最大化总重量），只需要调整DP数组的含义，追踪数组的逻辑是完全一样的。

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