正序/逆序问题：

优化成一维数组的情况，只有完全背包会正序遍历 j 。

因为一维数组的情况下，正序遍历如果背包剩余容积足够（j>v[i]），会重复装入一个物品，这是完全背包的思路。

逆序遍历则不会有重复的现象，因为前面的数据都为 0 。

从左往右更新有脏数据。

从右往左更新都是 0 。

小规律：

• 四种背包的朴素做法，也就是二维状态都是正序，一维都是倒序。

下面是一个很有参考价值的例子和过程模拟。

例子：假设有3件物品，背包的总体积为10

物品 体积 价值
i = 1 4 5
i = 2 5 6
i = 3 6 7
因为 f[0][j] 总共0件物品，所以最大价值为 0， 即 f[0][j] == 0 成立

如果 j 层循环是递增的： 
for (int i = 1; i <= n; i++) {
    for (int j = v[i]; j <= m; j++) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}
当还未进入循环时:
f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;

当进入循环 i == 1 时：
f[4] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;
f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;

重点来了！！！
f[8] = max(f[8], f[4] + 5); 即max(0, 5 + 5) = 10; 即f[8] = 10;
这里就已经出错了
因为此时处于 i == 1 这一层，即物品只有一件，不存在单件物品满足价值为10
所以已经出错了。

如果 j 层循环是逆序的：
for (int i = 1; i <= n; i++) {
    for (int j = m; j >= v[i]; j--) {
        f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
}

模拟过程如下：

当还未进入循环时:
f[0] = 0;  f[1] = 0;  f[2] = 0;  f[3] = 0;  f[4] = 0;  
f[5] = 0;  f[6] = 0;  f[7] = 0;  f[8] = 0;  f[9] = 0; f[10] = 0;

当进入循环 i == 1 时：w[i] = 5; v[i] = 4;
j = 10：f[10] = max(f[10], f[6] + 5); 即max(0, 5) = 5; 即f[10] = 5;
j = 9 ：f[9] = max(f[9], f[5] + 5); 即max(0, 5) = 5; 即f[9] = 5;
j = 8 ：f[8] = max(f[8], f[4] + 5); 即max(0, 5) = 5; 即f[8] = 5;
j = 7 ：f[7] = max(f[7], f[3] + 5); 即max(0, 5) = 5; 即f[7] = 5;
j = 6 ：f[6] = max(f[6], f[2] + 5); 即max(0, 5) = 5; 即f[6] = 5;
j = 5 ：f[5] = max(f[5], f[1] + 5); 即max(0, 5) = 5; 即f[5] = 5;
j = 4 ：f[6] = max(f[4], f[0] + 5); 即max(0, 5) = 5; 即f[4] = 5;

当进入循环 i == 2 时：w[i] = 6; v[i] = 5; 
j = 10：f[10] = max(f[10], f[5] + 6); 即max(5, 11) = 11; 即f[10] = 11;
j = 9 ：f[9] = max(f[9], f[4] + 6); 即max(5, 11) = 5; 即f[9] = 11;
j = 8 ：f[8] = max(f[8], f[3] + 6); 即max(5, 6) = 6; 即f[8] = 6;
j = 7 ：f[7] = max(f[7], f[2] + 6); 即max(5, 6) = 6; 即f[7] = 6;
j = 6 ：f[6] = max(f[6], f[1] + 6); 即max(5, 6) = 6; 即f[6] = 6;
j = 5 ：f[5] = max(f[5], f[0] + 6); 即max(5, 6) = 6; 即f[5] = 6;

当进入循环 i == 3 时: w[i] = 7; v[i] = 6; 
j = 10：f[10] = max(f[10], f[4] + 7); 即max(11, 12) = 12; 即f[10] = 12;
j = 9 ：f[9] = max(f[9], f[3] + 6); 即max(11, 6) = 11; 即f[9] = 11;
j = 8 ：f[8] = max(f[8], f[2] + 6); 即max(6, 6) = 6; 即f[8] = 6;
j = 7 ：f[7] = max(f[7], f[1] + 6); 即max(6, 6) = 6; 即f[7] = 6;
j = 6 ：f[6] = max(f[6], f[0] + 6); 即max(6, 6) = 6; 即f[6] = 6;

就模拟一下发现没有错误，即逆序就可以解决这个优化的问题了。

从1开始/从v[i]开始

• 从1开始的都是朴素二维数组做法。因为二维数组在j<v[i]时也要有数据，供后续状态转移时使用。

• 一维数组不需要。因为一维的情况下，赋值语句从f[i] [j] = f[i-1] [j] 变成了 f[ j ] = f[ j ] ,两者等价，但右式可以消掉。 判断语句挪到循环里，结束。

同理，省略的f[i] = f[i] 等价于 f[i][j] = f[i-1][j]

因为赋值语句里的 f[i] = f[i] ,右值为上一层循环里的 f[i] ，即 i - 1 。

这个f[j]还没有在第 i 层的循环里被更新过。

k的出现

k在多重背包、分组背包（特殊多重背包）、完全背包单独的朴素形式出现。

01背包只有选或不选两种情况，不需要 k 的引入。

完全背包一维形式在循环中已经包含了“重复调用，向上更新”的目的，不需要再引入 k。

这一点可以参考 正序/逆序问题。