[0/1具有最小成本的背包

Question

[著名的0/1背包问题着重于在给定的Weight (W)中获得最大成本/价值。

上面的代码是这个::

n = cost_array / weight_array size
INIT :: fill 0th col and 0th row with value 0
for (int i=1; i<=n; i++) {
            for (int j=1; j<=W; j++) {
                if (weight[i-1] <= j) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - weight[i-1]] + cost[i-1]);
                }else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

答案:: dp[n][W]

新问题 ::因此，这里我们要计算最大成本/价值。但是，如果我想找到最低的成本/价值（仍然仅限于背包）怎么办。

我认为问题归结为我如何执行上述INIT步骤。就像在循环中一样，我认为它将保持不变，唯一的区别是Math.max变为Math.min

我用INIT，Infinity等尝试了0步骤，但无法建立迭代解决方案。我们怎么可能那样做？

Answer 1

@ radovix提到的书面答案

• 将每个权重转换为负数并编写相同的算法。