[总结] 关于01背包和完全背包以及优化

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

今天晚上又被问起01背包和完全背包的遍历顺序了，我决定写一篇博文，这样再有人问我就可以直接把这篇文章发给他了。

我要不要先以我的方式来介绍一下这两个问题？首先我们知道01背包和完全背包的状态转移方程：

01背包：$f(i,j)=max{f(i-1,j), f(i-1,j-w_i)+v_i}$

完全背包：$f(i,j)=max{f(i-1,j),f(i-1,j-kw_i)+kv_i}$

简单解释一下，以01背包为例，我们定义$f(i,j)$为扫到第$i$个物品为止，背包容量为$j$时的最大价值。我们依次从第一个物品开始，决定要不要往这个背包里放，如果放的话，我们一定会从另一个状态转移过来，这个状态即扫到上一个物品、同时容量为$j-w_i$时的状态，为什么不是比$j-w_i$更小的一个状态？因为这个方程满足最优子结构：保证$f(i-1,j-w_i)$一定由上一个最优状态转移来，那么这个状态必然是最优的。完全背包也是如此，只不过朴素的做法需要多枚举一维第$i$个物品放的个数。

我们回到最开始的问题：01背包和完全背包的遍历顺序为什么会不一样？究竟有什么关系？

在我初学背包问题的时候也想到了这个问题，但是很久之后才去想着弄明白这件事。一般提出这个问题的是已经了解了这两种背包问题并且知道了他们的优化算法的同学。能提出这个问题也说明实际上并没有真正理解这两个状态转移的内涵（以及没认真看背包九讲2333）。

首先介绍一下01背包的优化，针对01背包的时间复杂度是无法再优化的了，但是朴素地开二维数组是冗余的。有人发现了这个问题，并且进一步发现了01背包的更新规律：在更新$i,j$时，并不会用到比$j$大的位置，即$f(i-1,k), k>j$。这很显而易见，因为物品的重量（花费）是大于等于0的，因此$j-w_i \leq j$

是一定成立的。所以我们才会有那个喜闻乐见的一位数组优化，只不过内层的更新顺序是从背包容量到物品重量（花费）的递减遍历顺序，这样能保证我们的递推是由扫到上一个物品时留下的数组中更新过来的，我贴一下喜闻乐见的代码：

1
2
3
4
5
for(int i = 1; i <= n; i++) {
    for(int j = m; j >= w[i]; j--) {
        dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    }
}

如果觉得还不够清楚，那我贴一个二维的、滚动数组形式的来帮你理解：

1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++) {
  for(int j = 0; j <= W; j++) {
    if(j < w[i]) {
      f[i][j] = f[i-1][j];
      continue;
    }
    f[i][j] = max(f[i][j], f[i-1][j-w[i]]+v[i]);
  }
}
1
2
3
4
5
6
7
8
9
for(int i = 1; i <= n; i++) {
  for(int j = 0; j <= W; j++) {
    if(j < w[i]) {
      f[i][j] = f[i-1][j];
      continue;
    }
    f[i][j] = max(f[i][j], f[i-1][j-w[i]]+v[i]);
  }
}

我们还会发现，一位数组优化后的代码更简洁，因为不需要转移$j<w_i$时的状态（一位数组里，不转移就直接保存在原位了）。

这就是为什么一位数组优化的01背包内层循环遍历顺序为什么是背包容量到物品重量的原因。

再看一下完全背包，我们朴素的完全背包更新是这样的：

1
2
3
4
5
6
7
8
9
10
11
for(int i = 1; i <= n; i++) {
  for(int j = 0; j <= W; j++) {
    if(j < w[i]) {
      f[i][j] = f[i-1][j];
      continue;
    }
    for(int k = 0; k * w[i] <= j; k++) {
      f[i][j] = max(f[i][j], f[i-1][j-k*w[i]]+k*v[i]);
    }
  }
}

多了一层，遍历物品件数，复杂度变高。

背包九讲里将完全背包转化为01背包来做，我们记得刚刚讨论过的01背包的一位数组优化，为了防止把扫到上一个物品的状态用扫到当前物品的状态更新掉，我们内层循环倒过来更新。但是反过来会发生什么呢？反过来的话，当我们更新$f(j)$的时候，会从$f(j-w_i)$更新过来，但此时$f(j-w_i)$或许已经包括了当前这个物品，那么$f(j)$再被此状态更新的话，实际上就相当于包括了两个物品$i$，这也是我们希望的，因为完全背包不限制每种物品数量，这也是这个优化成立的原因。贴份代码：

1
2
3
4
5
for(int i = 1; i <= n; i++) {
  for(int j = w[i]; j <= W; j++) {
    f[j] = max(f[j], f[j-w[i]]+v[i]);
  }
}