c++背包问题
老官童鞋gogo 人气:0又鸽了好久……
前言
博主刚刚学会背包问题不久,然后有一段时间没练习了
今天就来重新温习一下,顺手就写了这一篇博客。
好了,下面进入正题!
算法简介
背包问题是动态规划的一个分支
主要是分成了01背包、完全背包和多重背包。
下面从01背包开始讲解。
背包算法介绍
01背包
基本概念
01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包可谓是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。
问题雏形
有N件物品和一个容量为V的背包。第i件物品的体积是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
问题解答
了解了基本概念和问题雏形后我们就可以来想做题的方法了。
从题目里看,我们就能看出,01背包有个特点:每种物品仅有一件,可以选择放或不放。
所以我们就可以把每种情况都枚举一遍。
首先建立一个二维数组dp[][]表示价值,w[i]是每件物品的价值,c[i]是每件物品的体积
然后就想,由于它只有放和不放两种状态,我们就要比较这两种状态的价值,用max函数。
状态转移方程:dp[i][v]=max{dp[i-1][v],dp[i-1][v-c[i]]+w[i]}
其中,dp[i-1][v]表示不放该物品,dp[i-1][v-c[i]]+w[i]表示放入该物品。
这样做一个循环枚举各种情况即可。
for (i = 1; i <= n; i++) for (j = v; j >= c[i]; j--)//在这里,背包放入物品后,容量不断的减少,直到再也放不进了 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
最后的结果就是最大值。
还有一些优化的方法:01滚动和就地滚动。
01滚动:
我们可以看到每一行的结果实际上只与上一行有关,所以就可以01滚动——f[i][0,1] 一行记录前一行的值,另一行记录当前行的值……
所以,这是一种简化的好办法!
就地滚动:
就地滚动就是用一个一维数组,把之前的状态和当前的状态放在同一个数组,但是在写的过程中会有问题。
先上代码吧:
for(i=1 ; i<= n ; i++) for(j= c[i]; j<v ; j++) if(!dp[j-c[i]) dp[j] = dp[j-c[i]];
我们会发现,这样的话一个物品会被重复计算多次。
实战演练
问题1:采药
这是一个经典的问题哦!
飞机场:洛谷P1048 采药
问题解答(不可用于直接AC本题,可进行参考!)
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define inf 100000000 7 //状态:dp[i][j]表示考虑前i个草药,目前体积之和为j,可以获得的最大价值 8 //转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 9 //答案:dp[m][max(...)] 10 //不需要初始化,直接算 11 //复杂度:O(m*t) 12 int dp[105][1005],w[105],v[105]; 13 using namespace std; 14 int main() 15 { 16 int t,m; 17 cin>>t>>m; 18 for(int i=1;i<=m;i++) 19 { 20 cin>>w[i]>>v[i]; 21 } 22 for(int i=1;i<=m;i++) 23 for(int j=t;j>=0;j--) 24 { 25 if(j-w[i]>=0) 26 dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); 27 else 28 dp[i][j]=dp[i-1][j]; 29 } 30 int ans=0; 31 for(int i=0;i<=t;i++) 32 { 33 ans=max(dp[m][i],dp[m][i-1]); 34 } 35 cout<<ans; 36 return 0; 37 }
当然还有一种做法。可以直接使用一维数组:参见一本通。
完全背包
基本概念
这个问题非常类似于01背包问题,所不同的是每种物品有无限件,也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……取[V/c]件等很多种。
问题雏形
有 N 种物品和一个容量为 V 的背包,每种物品都有无限件可用。放入第 i 种物品的费用是 Ci ,价值是 Wi 。求解:将哪些物品装入背包,可使这些物品的耗费的费用总和不超过背包容量,且价值总和最大。
问题解答
这个题目有一个和01背包不一样的地方:每种物品有无数件!
然后我们想前面我说过的就地滚动,会计算多次,这不正巧?
实战演练
问题2:疯狂的采药
这个……这个题目的介绍不大正经,未成年人请在家长的陪伴下观看。
飞机场:洛谷P1616 疯狂的采药
问题解答(不可用于直接AC本题,可进行参考!)
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #define inf 100000000 7 //状态:dp[i][j]表示考虑前i个草药,目前体积之和为j,可以获得的最大价值 8 //转移方程:dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) 9 //答案:dp[m][max(...)] 10 //不需要初始化,直接算 11 //复杂度:O(m*t) 12 int f[1000001],t,m,ti,v; 13 using namespace std; 14 int main() 15 { 16 cin>>t>>m; 17 for(int i=1;i<=m;i++) 18 { 19 cin>>ti>>v; 20 for(int j=ti;j<=t;j++) 21 f[j]=max(f[j],f[j-ti]+v); 22 } 23 cout<<f[t]; 24 return 0; 25 }
多重背包
基本概念&问题雏形
有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件体积是w[i],价值是v[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。
问题解答
这个问题的特点是:每种物品有一定数量
这个运用的是二进制思想!
转化为01背包求解:把第i种物品换成n[i]件01背包中的物品,则得到了物品数为Σn[i]的01背包问题。
我们考虑把第i种物品换成若干件物品,使得原问题中第i种物品可取的每种策略——取0..n[i]件——均能等价于取若干件代换以后的物品。
另外,取超过n[i]件的策略必不能出现。 方法是:将第i种物品分成若干件物品,其中每件物品有一个系数,这件物品的费用和价值均是原来的费用和价值乘以这个系数。
使这些系数分别为1,2,4,...,2^(k-1),n[i]-2^k+1,且k是满足n[i]-2^k+1>0的最大整数。例如,如果n[i]为13,就将这种物品分成系数分别为1,2,4,6的四件物品。
解决问题的道理
1) 1+2+4+...+2^(k-1)+n[i]-2^k+1 = n[i] 这就保证了最多为n[i]个物品
2)1,2,4,……,2^(k-1),可以凑出1到2^k – 1的所有整数(联系一个数的二进制拆分即可证明,证明过程在下面的题解中)
3) 2^k……n[i]的所有整数可以用若干个上述元素凑出(可以理解为凑n[i]-t, 而n[i]为上面所有数的和,t则是一个小于2^k 的数,那么在所有的数中去掉组成2^k 的那些数剩下的就可以组成n[i]-t了)
当然,这个二进制的道理我在之前的一篇博客上写过,一会的实战演练会带你们去。
实战演练
问题3:宝物筛选
这是一道很水的蓝题……
飞机场:洛谷P1776 宝物筛选题解(我写的,你们还有更详细的多重背包解决思路)
后记
本文就写这么多了,背包问题在考试中会经常出现,希望大家深入理解其中的思想。
客官,给个赞再走呗?
加载全部内容