关于01背包
  • 板块学术版
  • 楼主AMIRIOX無暝
  • 当前回复11
  • 已保存回复11
  • 发布时间2020/11/14 18:37
  • 上次更新2023/11/5 08:03:59
查看原帖
关于01背包
320697
AMIRIOX無暝楼主2020/11/14 18:37

蒟蒻怎么也看不懂这个代码...

  1. 假设现在已经算到了将前 33 个物品放入大小为 33 的背包了(即i=3, j=3;前3个物品a b c的大小都是1), 那么算到装前四个的时候, 大小为 33 的背包已经被大小为1的a, b, c装满了, 按理第四个就不应该算了, 可代码写的是if(j>=w1[i]), 如果第四个物品价值也是1, 显然1<3, 那么还是会进行下去, 这样真的可以吗 ???
  2. 为什么选择装第 ii 个物品只是j-w1[i]?
  3. 如果只是从前向后遍历一遍每个物品, 会不会有比如第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];
        }
    }
}

人比较菜, 希望各位大佬不要喷我 ( ( (

2020/11/14 18:37
加载中...