可以用表格来理解 每次都要把容量用光.比如:5个容量 用掉了 4个容量后 也要上容量1的列里找到最大值加上.然后和之前的容量5 取max.
| (w ,v) | 编号/背包容量 | 5 | 4 | 3 | 2 | 1 | 0 |
|---|---|---|---|---|---|---|---|
| 1.2 | 0(能选1件) | 2 | 2 | 2 | 2 | 2 | 0 |
| 2.4 | 1(能选2件) | 6 = max( 4+2,2) | 6 = max(4+2,2) | 6 | 4 | 2 | 0 |
| 3.4 | 2(能选3件) | 8 = max( 4+4,6) | 6 = max(4+2,6) | 6=max(4,6) | 4 | 2 | 0 |
| 4.5 | 3(能选4件) | 8 = max( 5+2,8) | 6 = max(5,6) | 6 | 4 | 2 | 0 |
从这里也能看出最后v = 4时候就能取到8了 但v = 5的时候仍然存储着8.故最后不用遍历数组f(m)就是最大值.
for (int i = 1; i <= n; i ++ )
//i = 1 时 f[5 - 1] 都被赋值成2.最开始f[j]都是零的.
//i = 2 时 能选前两件物品了.容量允许的情况下,max
for (int j = m; j >= v[i]; j -- )
f[j] = max(f[j], f[j - v[i]] + w[i]);
这样对着一维度源码分析一下应该可以理解了.必须逆序
二维的也可以这样理解.把容量逆序与否都是可以的
滚动数组是不断覆盖掉用过但是不再需要的值.
郑未老师启发的思路.
