01背包-空间优化

「0-1 背包」问题，在草稿纸上多模拟几次填表的过程，不难发现：表格的空间可以重复使用。根据「0-1 背包问题」的状态转移方程：

可以知道，在状态转移的过程中：

• 当i >= 1 时，下标为 i 这一行的状态值 只参考了 下标为 i - 1 这一行，位于 dp[i][j] 正上方以及正上方的左边的单元格的状态值
• 当 i >= 2 时，在填写下标为 i 这一行的状态值时，下标为 i - 2 的行以及之前的行都不会再被参考
• 只输出最后一行最后一个状态值。

基于上面的事实，有以下两种方式进行空间优化，它们都是很典型的空间优化技巧。

空间优化：一维数组

状态值的更新只和它上边和左边的元素有关，我们可以把空间投影到一行，执行状态转移（填表）的时候，从右边到左边更新状态值。

• 在没有空间优化的时候，填写表格一开始的几个状态值，由于 weights[i - 1] > j，表示物品 i - 1（下标从 1 开始）不能装进背包，此时值需要从上一行「照抄」下来；
• 采用「逆序填表」的时候，当 j 减少到 weights[i - 1] > j，就退出了循环(所以前面的都可以照抄)，又由于只使用一行填表，等价于当 weights[i - 1] > j 时，将「上一行的值照抄到下一行」。

友情提示：「逆序填表」的技巧在初学的时候，相对不好理解，建议大家通过在纸上模拟填表的过程，帮助理解「逆序填表」的合理性。

  /**
   * @description: 
   * @param {number} W 背包大小
   * @param {number[]} weights 商品重量数组
   * @param {number[]} values 商品价值数组
   * @return {number} 能装入商品的最大价值
   */
  const backpack01 = function backpack01(W, weights, values) {
    // N为商品个数
    const N = weights.length;
    if (N == 0) return 0;
    const dp = new Array(W + 1).fill(0);
    // N个物品，所以从1开始
    // 添加一个重量为0的商品，导致后面使用的时候 i 要 -1
    for (let i = 1; i <= N; i++) {
      // j 从最大背包承重W开始, 
      for (let j = W; j >= weights[i - 1]; j--) {
        dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
      }
    }
    return  dp[W];
  }

复杂度分析：

时间复杂度：O(NW)，这里 N 是背包价值数组的长度，W 是背包的容量，时间复杂度没有变
空间复杂度：O(W)，使用了 W 大小的表格

优点：

• 由于空间消耗为常数级别，可以处理海量数据；

• 省去了「把上一行的结果先抄下来」这个步骤，减少了一定量的赋值操作。

  缺点：

• 初学的时候，如果对「状态转移方程」和「表格复用」的理解不是很充分，很可能是个难点；

• 表格复用会使得一些信息丢失。如果想要「通过结果得到满足条件的一个最优解」，表格复用的写法就不能达到目的。

建议：

如果对表格复用的写法不是很熟悉，不需要一步到位实现「空间优化」的写法。在绝大多数情况下，不优化空间问题不大：

• 一些在线判题系统（online judge）对空间消耗不会有很严苛的考察。先正确完成问题，保证「时间复杂度」最优即可；
• 如果是在面试中，可以和面试官说明自己知道空间优化的写法，但时间有限，先保证编码正确更重要。