锐客网

  1. 首页 > it技术 > >

背包四讲|背包四讲 (AcWing算法基础课笔记整理)

背包四讲

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkle和Hellman提出的。
---百度百科
本笔记参考视频与博客：
背包九讲专题_哔哩哔哩_bilibili
dd大牛的《背包九讲》 - 贺佐安 - 博客园 (cnblogs.com)
但是笔者做了简化，只选取了其中较为方便理解的4种背包问题进行详解，故取名为背包四讲（AcWing算法基础课四讲）。
  • 具体四种问题如下图：
背包四讲|背包四讲 (AcWing算法基础课笔记整理)
文章图片

0x1 01背包 问题描述
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
【背包四讲|背包四讲 (AcWing算法基础课笔记整理)】0 0 输入样例
4 5 1 2 2 4 3 4 4 5

输出样例
8

分析
朴素版做法
背包四讲|背包四讲 (AcWing算法基础课笔记整理)
文章图片

解答
#include #include using namespace std; const int N=1010; int n,m; int v[N],w[N]; //分别记录每个物品的体积和价值 int f[N][N]; //f[i][j]来记录前i个物品且体积不超过j的最大价值int main() { 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++) { //1.当前不把第i件物品放入背包 f[i][j]=f[i-1][j]; //2. //如果当前物品体积没有超过j(v[i]<=j)，则把第i件物品放入背包 //由于要选取第i件物品，之前之前的f[i-1][]不仅不能超过f[][j]，还要全部预留v[i]的体积空间。 //这样就得到了从前i-1个物品里选体积不超过j-v[i]的最大价值:f[i-1][j-v[i]],最后加上w[i]。 //这两种情况取最大者 if(v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); } } cout<

空间优化（一维化）
我们已经得到了朴素版做法。这里要注意背包问题的分析与代码的优化是没有关联的，一般是先根据分析，写出朴素做法，再经过推导得到优化代码。
分析：通过猜想，我们发现可以试图将 f[i][j] 降为成 f[j] 以优化空间。现在对原来代码进行修改。
for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { //当前不把第i件物品放入背包的情况可以直接删[i]与[i-1]， //因为f[j]=f[j]正好是把上层循环旧的f[j]更新掉 f[j]=f[j]; //当前物品体积没有超过j(v[i]<=j)，则把第i件物品放入背包的情况不能直接删, //因为j是递增的，而j-v[i]一定小于j， //所以下面的语句在给f[][j]赋值时，f[][j-v[i]]一定是先更新过的，所以就是最新的f[i][j-v[i]],我们知道f[i][j-v[i]]不一定等于f[i-1][j-v[i]]，这显然是不合题意的。 //if(v[i]<=j) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]); //所以简单写成下面这样是错误的 //if(v[i]<=j) f[j]=max(f[j],f[j-v[i]]+w[i]); //这里我们发现如果j从大到小循环，由于j是递减的，并且j-v[i]一定小于j，所以在赋值给f时j-v[i]是还未更新的上层循环值，也就是f[i-1][]的值，这样就符合题意。} }

修改后代码如下
for(int i=1; i<=n; i++) { for(int j=m; j>=0; j--) { f[j]=f[j]; f[j]=max(f[j],f[j-v[i]]+w[i]); if(v[i]<=j) f[j]=max(f[j],f[j-v[i]]+w[i]); } }

进一步删掉多余代码，整合判断条件后如下(终极版)：
#include #includeusing namespace std; const int N=1e3+10; int n,m; int v[N],w[N]; int f[N]; int main() { 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=m; j-v[i]>=0; j--) { f[j]=max(f[j],f[j-v[i]]+w[i]); } } cout<

总结
01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。
0x2 完全背包 问题描述
有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0 0 输入样例
4 5 1 2 2 4 3 4 4 5

输出样例：
10

分析
朴素版做法
背包四讲|背包四讲 (AcWing算法基础课笔记整理)
文章图片

解答
//朴素版做法 #include #include using namespace std; const int N=1010; int f[N][N]; int v[N],w[N]; int n,m; int main() { 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; k*v[i]<=j; k++)//不选的时候，k=0，0<=j恒成立，和题。 //选的时候，体积最大情况为只选当前第i件物品，只要k*v[i]不比j大就行。 { f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); } } }cout<

时间优化（简单推导）
上面朴素做法最坏情况为O(n*m^2) v[i]取1时 达到10^9, 在超时的边缘疯狂试探
我们决定对时间进行优化，观察发现
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...f[i-1][取到最小])
f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,...f[i-1][取到最小])
我们发现可以使用下面的f[i][j-v]+w替换上面的后半部分式子
故 f[i][j]=max(f[i-1][j],f[i][j-v]+w),此时的状态转移方程就得到了简化
简化版DP 时间复杂度O(n^2)
//时间优化 #include #includeusing namespace std; const int N=1e3+10; int n,m; int v[N],w[N]; int f[N][N]; int main() { 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]; if(j-v[i]>=0) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); } cout<

在时间优化基础上优化空间
//时间优化+空间优化 #include #includeusing namespace std; const int N=1e3+10; int n,m; int v[N],w[N]; int f[N]; int main() { 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=v[i]; j<=m; j++)//if(j-v[i]<0)循环会直接跳过，所以j从v[i]开始就好了。 { f[j]=max(f[j],f[j-v[i]]+w[i]); } cout<

总结
完全背包问题也是一个相当基础的背包问题。希望你能够对状态转移方程和优化的推导过程都仔细地体会，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。
0x3 多重背包 问题描述
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数，表示最大价值。
数据范围
由下面解法确定
输入样例
4 5 1 2 3 2 4 1 3 4 3 4 5 2

输出样例：
10

朴素版做法
数据范围
0 0 分析
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取 n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则：f[i][v]=max{f[i-1][j-k*v[i]]+ k*w[i]}。只不过每件物品有件数限制k<=s[i]。那么直接模仿照抄完全背包的朴素版本一定是可行的。
解答
#include #includeusing namespace std; const int N=1e4+10; int n,m; int v[N],w[N]; int f[N][N]; int s[N]; int main() { 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*v[i]<=j&&k<=s[i]; k++) { f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]); } } } cout<

但是这里我们想模仿完全背包时间优化的代码却不可以。
对于完全背包我们有
f[i][j]=max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w,...f[i-1][取到最小])
f[i][j-v]=max(f[i-1][j-v],f[i-1][j-2v]+w,...f[i-1][取到最小])
但是多重背包由于有件数限制，虽然下面的式子是成立的，但是f[i-1,j-sv]不一定能取到最小。
第二行多的f[i-1,j-(s+1)v]+sw使得我们的推导无法进行下去，因为从递推式中减去一项是不容易做到的。
背包四讲|背包四讲 (AcWing算法基础课笔记整理)
文章图片

时间优化（二进制优化）
数据范围
0 0 0 提示：
本题考查多重背包的二进制优化方法。
分析
由朴素做法的最后一段分析可知，我们需要一种新的方法来优化多种背包问题。否则是无法通过这一题的，因为时间复杂度超时。这里介绍二进制优化方法。
二进制优化方法原理浅谈
我们知道二进制由0和1两个数组成，任意的10进制数都可以由二进制数表示。
而0，1可以类比成背包问题的第i个数选（1）与不选（0）。
那么通过枚举全部（1，2，4，8，...，2^n）也就是二进制的(1，10，100，1000，10000，...)，这些数的选与不选就可以表示所有的10进制数。
例如：（十进制数）11=（二进制数）1000+10+1；只要选这三个数就可以表示11。
并且这些二进制数选与不选都是唯一的，所以相当于把问题转换成了01背包问题。
这种优化对于大数尤其明显，例如有1024个商品，在正常情况下要枚举1025次 ， 二进制思想下转化成01背包只需要枚举10次。
解答
这里我们直接写二进制优化+空间优化的版本（因为数据范围较大，不优化空间会MLE）
#include #includeusing namespace std; const int N=2e6+10,M=2010; int v[N],w[N]; int n,m; int f[M]; int cnt; int main() { cin>>n>>m; int a,b,s; //下面是二进制优化过程 for(int i=1; i<=n; i++) { cin>>a>>b>>s; for(int j=1; j<=s; j*=2)//把二进制件数（1，10，100，1000...）存进去 { cnt++; v[cnt]=j*a; w[cnt]=j*b; s-=j; } if(s>0)//这里s的值一定小于2^(j+1)，s为二进制表示循环后（s-=j; ）剩的数。 { cnt++; v[cnt]=s*a; w[cnt]=s*b; } }n=cnt; //一定要更新n的值，因为cnt才是二进制优化后的实际物品个数//下面和01背包空间优化代码一致 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<

总结
这里二进制优化十分的优雅，请务必在掌握前面几种背包题型后好好理解，运用。
0x4 分组背包 朴素做法
分析
背包四讲|背包四讲 (AcWing算法基础课笔记整理)
文章图片

解答
#include #includeusing namespace std; const int N=110; int n,m; int s[N],v[N][N],w[N][N]; //这里多一维记录这一组的第几个就好 int f[N][N]; int main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>s[i]; for(int k=1; k<=s[i]; k++) cin>>v[i][k]>>w[i][k]; }for(int i=1; i<=n; i++) { for(int j=0; j<=m; j++) { f[i][j]=f[i-1][j]; for(int k=1; k<=s[i]; k++)//唯一和01背包不同点，每一组的每个都要判断一遍，用循环写 { if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); } } }cout<

空间优化（一维化）
#include #includeusing namespace std; const int N=110; int n,m; int s[N],f[N]; int v[N][N],w[N][N]; int main() { cin>>n>>m; for(int i=1; i<=n; i++) { cin>>s[i]; for(int k=1; k<=s[i]; k++) { cin>>v[i][k]>>w[i][k]; //这里用k不用j，和下面代码保持一致，方便读者理解 } }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]); //借鉴01背包空间优化 } } } cout<

总结
分组的背包问题将彼此互斥的若干物品称为一个组，这建立了一个很好的模型。不少背包问题的变形都可以转化为分组的背包问题，由分组的背包问题进一步可定义“泛化物品”的概念，十分有利于解题。
小结 这四种背包问题被选入AcWing算法基础课动态规划第一章。大家应细细体会代码的优雅性，与推理的严谨性。作为学习算法的基础好好掌握。（基础不等同于简单，base != easy）由于笔者整理的较为仓促，难免有纰漏，欢迎评论指出。
最后引用 贺大牛的一句话送给大家，触类旁通、举一反三，应该也是一个OIer应有的品质吧。

    推荐阅读


    上一篇：小学期第一套题总结与反思

    下一篇：如何维护一个巨大的Android项目呢（阿里大佬分享的高级Android|如何维护一个巨大的Android项目呢？阿里大佬分享的高级Android 组件化实战，你确定不看看）