蒟蒻怎么也看不懂这个代码...
- 假设现在已经算到了将前 3 个物品放入大小为 3 的背包了(即i=3, j=3;前3个物品a b c的大小都是1), 那么算到装前四个的时候, 大小为 3 的背包已经被大小为1的a, b, c装满了, 按理第四个就不应该算了, 可代码写的是
if(j>=w1[i])
, 如果第四个物品价值也是1, 显然1<3
, 那么还是会进行下去, 这样真的可以吗 ???
- 为什么选择装第 i 个物品只是
j-w1[i]
?
- 如果只是从前向后遍历一遍每个物品, 会不会有比如第1个物品和第10个物品无法装到一起去计算的问题?而且根据dp的最优子结构, 计算完一个阶段的时候就应该已经是最优解, 我都没考虑后面的物品怎么得出的最优解呢?
for(i=1;i<n;i++) {
for(int j=0;j<=w;j++) {
if(j>=w1[i]) {
dp_1[i][j]=max(dp_1[i-1][j],dp_1[i-1][j-w1[i]]+v[i]);
}else {
dp_1[i][j]=dp_1[i-1][j];
}
}
}
人比较菜, 希望各位大佬不要喷我 ( ( (