著名的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但无法构建迭代解决方案。我们怎么可能做到这一点？
写@radovix提到的答案
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句