AcWing动态规划基础学习——背包问题

本文主要参考AcWing算法基础课相关内容，用于学习记录与分享，如有侵权请联系我删除。

一、0-1背包问题

概述：给定一组物品，每个物品有重量和价值，在限定的总重量内选择物品，使得总价值最大。每个物品最多只能选择一次（选或不选）。

问题描述：物品重量数组 w，物品价值数组 v，背包容量 W。在不超过背包容量的情况下，问能装入物品的最大价值。

思考方式：0-1背包问题都可以按照下图来分析

简单引例：AcWing2.01背包问题

C ++ 代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 1010; //v表示物品体积 w表示物品价值 int v[N], w[N]; //创建状态表示集合 int dp[N][N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { //状态计算 //不含i时 dp[i][j] = dp[i - 1][j]; //含i时,只有当前j >= v_i,即能装的下v_i时才含i if(j >= v[i]) dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); } } cout << dp[n][m]; return 0; }

优化思路：

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）状态f[j]定义：N件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

（3）为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

（4）不理解看看这个 例如，一维状态第 i 轮对体积为 3 的物品进行决策，则f[ 7 ]由f[ 4 ]更新而来，这里的f[ 4 ]正确应该是 f[ i - 1 ][ 4 ]，但从小到大枚举 j 这里的 f[ 4 ] 在第i轮计算却变成了 f[ i ][ 4 ]，我们需要的是 f [ i - 1 ][ 4 ]而不是 f[ i ][ 4 ]，正序的话 f[ i - 1 ][ 4 ]就会被 f[ i ][ 4 ]覆盖。当逆序枚举背包容量 j 时，我们求 f[ 7 ]同样由 f[ 4 ]更新，但由于是逆序，这里的f[ 4 ]还没有在第i轮计算，所以此时实际计算的 f[ 4 ]仍然是 f[ i - 1 ][ 4 ]。

（5）简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

一维状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i])。

for(int i = 1; i <= n; i++) 
    for(int j = m; j >= 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 优化前
            f[j] = f[j];            // 优化后，该行自动成立，可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后
    }    
实际上，只有当枚举的背包容量 j >= v[i] 时才会更新状态，因此我们可以修改循环终止条件进一步优化。

优化后一维代码：

for(int i = 1; i <= n; i++) { //0-1背包 j 要逆序     for(int j = m; j >= v[i]; j--)           f[j] = max(f[j], f[j - v[i]] + w[i]); } 

二、完全背包问题

与0-1背包类似，主要区别在于每种物品可以选取无限次。

问题描述：给定一个容量为( W )的背包和( n )种物品，每种物品有重量( w_i )和价值( v_i )，求在不超过背包容量的前提下，能装入物品的最大价值总和。

思考方式（朴素方法）：与0-1背包的区别在于集合的划分不同，这里是将集合划分成k + 1段，k 的含义是： j 的空间先装 0 个 i 物品、1 个 i 物品、2 个 i 物品...直至装到 k 个 i 物品时再也装不下。

最终状态计算：f [ i ][ j ] = max(f [ i ][ j - v_i * k] + w_i * k), k = 0, 1, 2, ...

简单引例：AcWing3.完全背包问题

C ++代码（可能会超时）：

#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { for(int k = 0; v[i] * k <= j; k ++) { f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k); } } } cout << f[n][m]; return 0; }

优化思路一：朴素方法困扰我们的主要是三层循环导致超时，这是由于状态计算和 k 相关。由下图我们可以观察到 f [ i ][ j ] 和 f [ i , j - v ]的计算公式部分很相似，只相差 w ，从而我们可以得到优化后的公式：f [ i ][ j ] = Max(f [ i - 1][ j ], f [ i, j - v_i] + w_i)，这样就和 k 无关了。

优化后代码（二重循环）：我们可以发现，与0-1背包二维代码相比仅有细微区别。

0-1背包状态计算：f [ i ][ j ] = Max(f [ i - 1][ j ], f [ i - 1, j - v_i] + w_i)，从 i - 1 层转换

完全背包状态计算：f [ i ][ j ] = Max(f [ i - 1][ j ], f [ i, j - v_i] + w_i)，从 i 层转换。

#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N][N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { f[i][j] = f[i - 1][j]; //与0-1背包问题的区别仅在f[i][j - v[i]] + w[i]; if(j >= v[i]) f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]); } } cout << f[n][m]; return 0; }

于是与0-1背包优化一样，可以对上述代码再进行一维优化得到最终版本。

完全背包最终版代码（一维数组）：

#include <iostream> #include <algorithm> using namespace std; const int N = 1010; int v[N], w[N]; int f[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i]; for(int i = 1; i <= n; i ++) { //这里是 j 是正序，由于是从 i 层转换不存在数据覆盖问题 for(int j = v[i]; j <= m; j ++) { f[j] = max(f[j], f[j - v[i]] + w[i]); } } cout << f[m]; return 0; }

三、多重背包问题

与0-1背包问题（每种物品只能选一次）和完全背包问题（每种物品无限次选择）不同，多重背包问题中每种物品有固定的数量限制。

问题描述：给定一个背包容量为 ( W )，以及 ( n ) 种物品，每种物品有三个属性：重量 ( w_i )，价值 ( v_i )，数量 ( s_i )（表示第 ( i ) 种物品最多可以选择 ( s_i ) 次）。目标是在不超过背包容量的前提下，选择物品的组合使得总价值最大。

思考方式（朴素方法）：与完全背包问题几乎完全相同，唯一的区别在于完全背包是装到装不下，这里是装到 s_i 个，即 k 的取值为：0，1，2，3，...，s_i；

最终状态计算：f [ i ][ j ] = max(f [ i ][ j - v_i * k] + w_i * k), k = 0, 1, 2, ..., s[ i ]

简单引例：AcWing4. 多重背包问题 I

朴素三重循环（可能会超时）代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 110; int v[N], w[N], s[N]; int f[N][N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i]; for(int i = 1; i <= n; i ++) { for(int j = 0; j <= m; j ++) { for(int k = 0; k <= s[i] && k * v[i] <= j; k ++) { f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k); } } } cout << f[n][m]; return 0; }

尝试完全背包的优化方式列出多重背包的 f[ i ][ j ] 和 f[ i ][ j - v]的表达式：

会发现 f[ i ][ j - v] 最后会多出一项f [ i−1, j−(s_i+1) *v] + s_i * w，这是为什么呢？

不理解看这里 这里是在分析 f[ i, j−w ]这个状态的表达式，首先这个状态的含义是从前 i 个物品中选，且总体积不超过 j-w 的最大价值，我们现在最多只能选 s 个物品，因此如果我们选 s 个第 i 个物品，那么体积上就要减去 s∗v，价值上就要加上 s∗w，那更新到状态中去就是 f[i−1,j−v−s∗v] + s∗w，表现出来就是多出一项（其实不是多，只是二者项数一样，由于错位对齐看起来多）。

那为什么完全背包不会有最后一项？
完全背包由于对每种物品没有选择个数的限制，所以只要体积够用就可以一直选，其结束的条件一样就是当装到不能再装时停止，表现出来就是对齐的样子（其实完全背包的 f[ i, j - v]要比 f[ i, j ]少一项）。

为什么不能用像完全背包一样去优化？简单来说就是我们不能通过总的最大值和最后一个数的最大值来求前面的最大值是多少，可参考视频

正确优化—二进制优化方式 ：

首先，借助0-1背包的思想，对每种物品的每一个都进行取或不取的判断，但是这样又太多了，复杂度为N*V*S，很容易超时。

我们知道任意一个实数可以由二进制数来表示：

1可以表示0~1；

1，2可以表示0~3；

1，2，4可以表示0~7；

1，2，4，...，2的k次方可以表示0~2的(k+1)次方 - 1；

比如对于200个物品，我们如果对每一个都进行取不取的判断，需要200次；但借助二进制我们知道200可以由1，2，4，8，16，32，64，73八组来表示，这样只需要判断8次，大幅减少了我们判断的次数。

于是借助二进制优化的思维可将，先将每种物品进行分组，再来一次0-1背包的判断就可以得出结果，复杂度降为N*logS*V。

最终代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 25000, M = 2010; int v[N], w[N]; int f[M]; int main() { int n, m; cin >> n >> m; //新组号 int cnt = 0; //对于每一种物品都进行二进制优化分组 for(int i = 1; i <= n; i ++) { int a, b, s; cin >> a >> b >> s; int k = 1; while(k <= s) { cnt ++; v[cnt] = a * k; w[cnt] = b * k; s -= k; k *= 2; } if(s > 0) { cnt ++; v[cnt] = a * s; w[cnt] = b * s; } } //此时n应该为新分组的组数 n = cnt; //进行0-1背包判断 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]); } } cout << f[m]; return 0; }

四、分组背包问题

分组背包问题是动态规划中背包问题的变种，其特点是将物品分为若干组，每组内的物品互斥，即每组只能选择一个物品或不选。目标是在背包容量限制下，选出物品组的最优组合，使得总价值最大。

分组背包问题其实类似于0-1背包问题，就是每次需要判断每组物品中选哪一个。

状态计算：f[ i ][ j ] = Max( f[ i -1][ j ], f[ i - 1, j - v[ i ][ k ]] + w [ i ][ k ] );

简单引例：AcWing9. 分组背包问题

这里直接上一维优化后的代码：

#include <iostream> #include <algorithm> using namespace std; const int N = 110; int v[N][N], w[N][N], s[N]; int f[N]; int main() { int n, m; cin >> n >> m; for(int i = 1; i <= n; i ++) { cin >> s[i]; for(int j = 1; j <= s[i]; j ++) { cin >> v[i][j] >> w[i][j]; } } //整体还是0-1背包的模板 for(int i = 1; i <= n; i ++) { for(int j = m; j >= 0; j --) { //对每组的每一个物品进行判断 for(int k = 1; k <= s[i]; k ++) { if(j >= v[i][k]) f[j] = max(f[j], f[j - v[i][k]] + w[i][k]); } } } cout << f[m]; return 0; }