背包问题
背包问题
一、01背包
问题描述
有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求背包能够装的物品价值最大是多少？
之所以叫01背包问题，是因为对于每一个物品，只有两种选择，要么拿，要么不拿，不能拆分。最终的取舍的结果可以用一个n维向量来表示，每一个分量只有0或1两种状态。
很明显，无论是优先考虑总价值大的还是单位价值大的，都不一定能够使最终拿到的价值总和最大。因为这两种方案都不一定能够充分利用背包的空间。暴力法一共有2N种可能，指数级别的运算量，显然不可取。
模拟真实情况的话，实际上难以决策是因为背包太大或者物品太多。如果背包只能装下1个物品或者只有1个物品，那么就很容易解决。也就是说，如果能够把复杂问题转化为稍简单一点的问题，然后再一步一步简化，最终就能够解决问题。
假如函数f(i,v)表示i个物品，放入体积为v的背包中这一问题的解。对于第i件物品，如果不拿，那么f(i,v)=f(i-1,v)，也就是说，不拿第i件物品的话，那么问题就等于只有i-1个物品，放入体积为v的背包中;如果拿，这时首先要背包放得下，也就是说，之前的i-1个物品最多只能占用v-c[i]的空间，那么之前i-1个物品的解就是f(i-1,v-c[i])，拿了之后的解就是f(i-1,v-c[i])+w[i]，也就是说f(i,v)=f(i-1,v-c[i])+w[i]。要使得最后拿到的物品的价值最大，那么f(i,v)=max(f(i-1,v),f(i-1,v-c[i])+w[i])。如此递推下去，f(1,v)是很好求解的，就是体积小于v且价值最大的那一个。并且还可以继续递推到f(0,v)，f(0,v)的最优解显然是0，意思就是没有物品可以选择，那么装入背包的物品总价值最大就是0。这里顺便补充一下，有些题目要求是恰好装满背包，那么，就只有f(0,0)=0，f(0,1)、f(0,2)……都不存在最优解，可以用-∞表示。
具体的程序显然可以采用递归，但是这个问题要采用动态规划（dynamic programming）。都是化繁为简，区别在于，采用递归算法，一般来说子问题是不相关的，也就是说，每一个子问题只需要算一次。而前面的分析可以看出，背包问题把一个问题分解成两个子问题，两个子问题继续分解，显然越往后问题分解得越多，关键很多是重复的。这种情况下，采用递归计算，将会有大量的重复计算，效率很低。为解决此问题，动态规划法采用的办法是先计算子问题，并且把子问题的解保存下来，然后逐步构建繁杂问题，直至最后的解。对于01背包问题，可以定义一个N行V列的二维数组dp[N+1][V+1]，用来保存f(i,v)的解，这一个表可以从左至右、从上到下来填，第0行表示没有物品可选时，全为零，第1行表示只有第1个物品可选时，第2行表示有第1、2个物品可选时，……，从列来看，第0列表示背包容量为0，当然也是全为0，第1列表示背包容量为1，第2列表示背包容量为2时，……直到第V列。
具体的程序如下：
#include <iostream>
using namespace std;
int main(){
int N,V;
int c[301],w[301];
int dp[301][101];
while(!(cin>>V>>N).eof()){
for(int i=1;i<=N;i++)
cin>>w[i]>>c[i];
for(int i=0;i<=N;i++)
dp[i][0]=0;
for(int j=0;j<=V;j++)
dp[0][j]=0;
for(int i=1;i<=N;i++)
for(int j=1;j<=V;j++){
if(j<c[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
}
cout<<dp[N][V]<<endl;
}
}
上面这段程序，硬编码了用到的数组的大小，其中dp数组定义的列只有101也就是只能处理背包大小100以下的问题，这是因为，二维矩阵太占空间了，太大以后程序运行不起来，一运行就出错。所以，必须对程序进行优化。优化分为空间优化和时间优化。
首先空间优化
从前面的分析及程序代码可以看出，处理第i行时实际上只用到了第i-1列的数据，所以，二维矩阵最多要2行就够了，前提是要『滚动』使用，可以采取处理完一行之后，把这一行复制到前一行去的办法。第0行是全0，不用复制，程序直接从第1行开始，处理完一行，就把这一行复制到第0行，然后仍然在第1行上进行下一轮循环。既然行是如此，那么列呢？显然，在处理j列时也只用到了前一行的第j列和第j-v[i]列也就是只用到了前面的列，那么如果j从V递减处理行不行呢？没什么问题，程序从第1行开始，用到的第0行是全0，无论从大到小还是从小到大都行，并且，这样调过头来处理，前面说把第1行复制到第0行就没必要，因为在处理第j列时，实际上只要用到但不会动到j前面的列的，也就是说可以直接在原来的行处理，不用读前一列的数据，就直接读本列是一样的。也就是说前面程序中dp[i-1][j]和dp[i-1][j-c[i]]只要j从大递减下来，就跟dp[i][j]和dp[i][j-c[i]]是一样的，因为如果用复制的办法来『滚动』使用，那肯定是一样的，因为j从大到小处理，还没有处理（影响）到。也就是说前面程序中的内循环，改成下面这样结果是一样的。
if(j<c[i])
dp[i][j]=dp[i][j];
else
dp[i][j]=max(dp[i][j],dp[i][j-c[i]]+w[i]);
每次都是处理同一行，那就用不着这么多行了。只留1行，也就是一维数组就够了。并且，很明显，那么if……else……都多余了，只需要if就够了。然后，实际上，for循环只需要j>=c[i]就够了，因为背包已经装不下第i个物品，显然已经不需要计算。那么在for循环内部，if都用不着了。
然后，性能优化。也就是减少一些不必要的运算。从程序可以看出，程序事实上最后只要dp[N][V]的值，而确定dp[N][V]的值实际上只需要用到dp[N-1][V]和dp[N-1][V-c[N]]的值，更小的列不用去判断，自然也不需要去算了。什么意思呢？意思是，在处理倒数第二个物品时，最多考虑留下能装下最后一个物品的空间就行了，没必要考虑留更多的空间。当然，同理，再处理第i个物品的时候，最多考虑到dp[i][V-ΣinCi]这一列就够了，更小的列不用计算，因为后面用不着，用得着就不是最优解，因为这时背包能够把后面剩下的都装下。不过，当物品很多的时候，仅仅用这个优化还不够，因为这样考虑留空间得留很多才够，这时v值都已经很小甚至计算的话都成负值了。另一方面，在处理第i个物品时，主要考虑的是能不能放下它，至于后面还有剩下多少物品，并不是这时需要考虑的，因为按照前面的推理，就能够达到最优，至于后面也许会剩下很多物品没办法放，那也是因为背包容量小的问题，也就是说在第i步，对v的遍历，并不需要考虑比第i个物品体积还小的v，也就是v只需要从V到c[i]就够了，那么综合起来，内循环的v只需要从V到max(V-Σ,c[i])。改进后的程序如下：
#include <iostream>
using namespace std;
int main(){
int N,V;
int c[301],w[301],acc[301];
int dp[20001];
while(!(cin>>V>>N).eof()){
int sum=0;
for(int i=0;i<=V;i++)
dp[i]=0;
for(int i=1;i<=N;i++){
cin>>w[i]>>c[i];
sum+=c[i];
}
for(int i=1;i<=N;i++){
int tp=max(V-sum,c[i]);
for(int j=V;j>=tp;j--)
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
sum-=c[i];
}
cout<<dp[V]<<endl;
}
}
二、完全背包
01背包问题每种物品只有1个，完全背包问题是每种物品可以有无限多个。其实，在01背包中，c[i]、w[i]并没有互不相同的要求，所以完全背包问题完全可以把每种物品看成是多个（不可能是无限，因为背包体积有限，最多V/c[i]个）物品，转换成01背包问题来解决。当然，这样的话，程序里就得在数组c、w中插入若干项，如果数组本身较大，比较麻烦。
采用01背包问题同样的分析方法，区别就在于对于第i个物品，可以取0、1、2、……个而不仅仅是0或1个。dp[i][j]=max(dp[i-1][j-kc[i]]+kw[i])(0<=k<=[j/c[i]]);当k只能取0、1时，其实就是01背包问题。
具体的写代码的话，上面这个转移方程本身就需要一个循环(k从0到[j/c[i]])，而无论k为何值，这里j-k*c[i]的意义只不过是背包的容量，所以只需要在遍历j时把j的范围控制好就可以达到同样效果。程序代码如下：
#include <iostream>
using namespace std;
int main(){
int N,V;
int c[301],w[301],acc[301];
int dp[20001];
while(!(cin>>V>>N).eof()){
for(int i=0;i<=V;i++)
dp[i]=0;
for(int i=1;i<=N;i++){
cin>>w[i]>>c[i];
}
for(int i=1;i<=N;i++){
for(int j=c[i];j<=V;j++)
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
}
cout<<dp[V]<<endl;
}
}
对比01背包的代码，差别不大，主要是内循环一个是向后遍历一个是向前遍历。为什么会这样呢？首先要明确的是，这两段代码都是空间优化后的结果，按照分析的结果，应该是用二维数组来保存子问题结果的。而如果用二维数组，那么01背包内循环向前遍历还是向后遍历，是无所谓的。因为在01背包问题里面，对于第i个物品，只有选或不选两种情况，需要比较的只是dp[i-1][j]和dp[i-1][j-c[i]]+w[i]这两种解的大小，实际上都是利用没有i这个物品时的两个解。而为了用一维数组来保存中间结果，采取j从后向前遍历，这样保证不会覆盖前面已经计算过的更小的j的计算结果。但是完全背包问题与01背包不一样的是：在选择第i个物品时，不仅仅要考虑不选择和选择1次的情况，还要考虑选择2次、3次甚至更多的情况，这个时候如果还采用向前遍历，因为一开始j比较大，此时如果只考虑放1个j物品，那么背包可能还有很多剩余空间，不能保证是最优解；而如果考虑放v/c[i]个i物品，则跨度太多，同样也不能保证是最优解，所以只能从少到多依次比较。如果当j=V时，不仅仅考虑v/c[i]个i物品而是考虑1、2、……个i物品，那么就跟前面分析的一样，这里又嵌套了一个循环，复杂了。而采取向后遍历，注意j的初值，实际上第1次内循环相当于是没有选择i物品时和选择1个i物品比较，然后，当j递增到k=2时，就是用选择2个i物品和选择1个i物品比较，如此类推，正好不会覆盖前面i-1个物品的计算结果。……所以，对于完全背包问题，j向后遍历是合理的、自然的。
那么新的问题出现了。01背包问题和完全背包问题的差别就在于选择i物品时，01背包问题可能考虑选择0个或1个，而完全背包问题可以考虑选择0、1、2、……个。那么01背包问题的内循环，能不能改成向后遍历呢？显然是不行的，不仅仅是覆盖不覆盖历史数据的问题，从算法上来讲，01背包只考虑选不选择i物品，那么比较了1次之后，后面是不用比较了，因为不能选择i物品多次，也就是j很小时循环就可以中止了。后面的结果就是第1次的结果，这就意味着，背包的剩余空间根本就没有去考虑。跟踪程序计算过程（填表过程）就相当于是依次放入物品直到最后，这怎么可能是最优解呢？从这里可以看出：01背包问题与完全背包问题很相似，解法也相似，但是却不能说01背包问题是完全背包问题的特例，因为用一般方法解决特殊问题应该总是可行的，所以，它们不是一般与特殊的关系，而是不同的问题（条件不同，并不是某一个变化因素变成固定）。
三、多重背包
多重背包问题与完全背包问题相似，只不过第i种物品的个数限制为p[i]个。这个问题显然不能用完全背包的解法，因为在考虑第i个物品时，p[i]个i物品不一定足以装满背包，这时计算出来的解就不一定是最优解，那么最后也就计算不出最优解了。但是，很明显可以转化为01背包问题来求解。转化为01背包问题就是把第i个物品拆分，当然不必拆分成一个一个的，可以把p[i]拆分成1、2、4、……、2k-1、p[i]-2k+1。为什么可以这样拆分呢？只为01背包问题无非是某个物品选与不选的问题，而多重背包问题实际是对于某个物品选择0、1、2、……、p[i]个的问题，无论选几个，都可以变成1、2、4这一个等比数列（最后一项表示全部加起来等于p[i]）的选与不选的组合。这有点像二进制，用每一个位来表示选与不选，就不必分解成很多项了。分解问题解决了，计算的时候，也不能真的在原数组中去插入若干项，只能在计算时想办法，顶多就是多一重循环的事。完整的程序代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int dp[30001];
int V,N;//背包容量、物体种类数
void CompletePack(int w,int v){
for(int i=w;i<=V;i++)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
void ZeroOnePack(int w,int v){
for(int i=V; i>=w; i--)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
int main(){
int n,v,w,m;//v物品价值，w物品重量，m物品件数
cin>>n;
while(n--){
memset(dp,0,sizeof(dp));
cin>>V>>N;
for(int i=0;i<N;i++){
cin>>v>>w>>m;
if(w*m>=V)
CompletePack(w,v);
else{
int k=1;
while(k<m){
ZeroOnePack(k*w,k*v);
m-=k;//m每次减少，但因为等比数列{2^n}的前n-1项之和等于n项-1，所以并不会影响循环次数；但最后求出了余数。
k<<=1;//k每次乘2，得到1、2、4、8、……2^(n-1)
}
ZeroOnePack(m*w,m*v);
}
}
cout<<dp[V]<<endl;
}
}
上面的这段程序结合和01背包和完全背包，采用的是二进制拆分法。看得出，采用二进制拆分法多了一重循环，这一重循环的次数大约是log2m次。
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
for(int k=1;k<=p[i] && k*c[i]<=j;k++)
dp[i][j]=max(dp[i][j],dp[i-1][j-k*c[i]]+k*w[i]);
这段代码是完全背包或者多重背包的处理过程，计算dp[i][j]需要考虑选择0个、1个还是多少个i物品，最内层的循环就是枚举可能选择的i物品的个数k，可选择的个数的范围跟j的大小有关，当j比较小时，可以选择的余地就小。随着j的增大，k的范围也增大，对于完全背包来说，总可以找到适当的k，使得j-k*c[i]足够小，也就是k、k-1、……、2、1、0这个比较链条足够长，可以把0、1的比较结果保存在1位置，1、2比较的结果保存在2位置，……，这样下去，所有的k值都纳入了判断中，所以k这层循环就不必要了。但是，对于多重背包来说，就不能这样，因为k还有限制，依次比较不能足以满足j值较大的需要，所以这时k的循环不能省略。无论是完全背包还是多重背包，当j比较小时dp[i][j]是比较容易确定下来的，只不过完全背包问题把dp[i][j]保存下来可用于后面的选择，但是多重背包的情况下，反而可能会覆盖上一层计算的结果。举例说明：当V=10，c[i]=2，p[i]=3时
dp[i][10]=max(dp[i-1][10]，dp[i-1][8]+2w[i]，dp[i-1][6]+4w[i]，dp[i-1][4]+6w[i]) dp[i][8]=max(dp[i-1][8]，dp[i-1][6]+2w[i]，dp[i-1][4]+ww[i]，dp[i-1][2]+6w[i])
也就是说，计算dp[i][10]时，需要用到dp[i-1][8]，如果采用向右遍历j，就要采用二维数组来保存中间状态，如果采用一维数组，那么dp[8]被覆盖，计算dp[10]的时候就会被影响。当然，向左遍历就不会有问题。下面，暂时按照向左遍历的思路考虑算法。
首先，会受影响的值是分组的，相关性也是分组的。分组实际上就是模c的同余类（余数相同），设V=ac[i]+b，所以只需要遍历模c的余数b，然后计算组内所有的dp，就可以处理完所有的j。之前分析的dp[i][j]在哪一组，实际上就是看j%c。如果采用循环遍历余数b，那么在组内部b就是固定的常数。把j=ac+b代入原来的状态转移方程。得到：dp[i][j]=max(dp[i-1][ac+b-kc]+kw)=max(dp[i-1][b+(a-k)c]+kw)在这个式子中，b是常数(前述)，c、w是i物品的重量和价值，也是常数，变化的就是k和a。k在原来的式子中是用来枚举选取i物品个数的，可能的取值范围在[0,min(j/c,p)]之间，a=j/c，j是当前背包容量，显然，0≤j≤V，那么0≤a≤V/c，所以0≤a-k≤V/c。所以，可以令a-k=k’，则k=a-k’，原式变成了。dp[i][j]=max(dp[i-1][b+k’c]-k’w+aw)，在需要比较的一组数里a也是固定的常数，所以可以把aw提出来，即dp[i][j]=max(dp[i-1][b+k’c]-k’w)+aw，到这里，要求最大值的式子已经和j没有关系了，只跟k’有关，k’=a-k，a=j/c也就是要计算的背包容量可以放的最多的i物品个数。k代表的是取i物品的个数，k取0、1、2、……对应的k’就取a、a-1、……，k与k’是对称的，反过来也一样。意思就是说，在考虑j空间放i个物品时，首先放i物品直到放不下，剩余的空间用前面i-1个物品填充，此时i物品有a个，得到一个总价值，然后，取出1个i物品和其他物品，再用前面i-1个物品重新填充，又得到一个总价值，如此下去，直到i物品全部取出来，比较这一系列的总价值，就得到最优解了（实际上也不是一直要比较到把所有i物品全部取出，最多比m个）。k’表示的是取出来的i物品个数，其取值范围和k一样，仍然是在[0,min(j/c,p)]之间(能装多少个，最多也就只能取出那么多个)。这样，需要计算最大值的式子就已经和j没有关系了。
现在求解的过程已经变成了在一系列dp[i-1][b+k’c]-k’w当中找最大值，并且这一系列数是随着k’的取值范围扩大（也即是j的增大）而逐渐增多，一开始只有1个(k’=0)，然后增加到2个(k’=0,1)，……直到V/c个。也就是说，只要遍历了k’，就相当于是遍历了j。在这种不断增大的数列里，求最值是很容易的。一开始只有1个，那自然是不用说，后面增加数的时候，如果加入的数比队尾小就加入队尾，否则就把原来的数从队尾退出，直到队尾比要加入的数大或者队列空了再加入。当然，每一次操作前，先要检查队列是否满了，满了的话要先把队首出队。这样操作下来，随时排在队首的都是当时的最大值。这样的队列叫做单调队列，因为队列里的元素随时是保持单调递减（或增）的，这种情况下不需要刻意去排序，也不需要在中间插入。即便是待加入的数在中间，这个时候入队只需移动队尾指针，而不是像插入排序那样去依次交换数据，因为小的数已经没有用处，不必要在保留。所以，在这种情况下，用单调队列找一个变化的区间的最值的效率非常高。需要注意的是，找到最大值后并不出队，出队只有在队列满了且还要加入值（窗口移动）或有更大的值的时候，队列满的意思每一次最多比较m个数，因为i物品只有m个，不可能有多于m种取法，所以在这里维护的队列最大长度为m。
在遍历k’找最大值的过程中，k’实际上始终等于最多可能取到的i物品的个数，也即k’与a是一样的。所以，j=k’c+b，然后比较前减掉的k’w再加回去（公式里面是加a*w），所以，最终得到dp[i][j]=max(dp[i-1][b+k’c]-k’w)+k’w。完整的代码如下：
#include <iostream>
#include <cstring>
using namespace std;
int dp[30001];
int V,N;//背包容量、物体种类数
struct {
int value;
int pos;
}que[30001];
int main(){
int n,v,w,m;//v物品价值，w物品重量，m物品件数
cin>>n;
while(n--){
memset(dp,0,sizeof(dp));
cin>>V>>N;
for(int i=0;i<N;i++){
cin>>v>>w>>m;
if(w*m>=V) m=V/w;//此时，相当于完全背包
for(int b=0;b<w;b++){//枚举余数
int head=0,tail=0;//队列初始化
for(int k=0;k<=(V-b)/w;k++){//k是表示背包可以放下的物品i的个数，必须遍历完，而不能只遍历到实际个数m
int x=k;
int y=dp[k*w+b]-k*v;
while(head<tail&&que[head].pos<k-m)head++;//判断队列长度，超长就出队，等于是移动“窗口”
while(head<tail&&que[tail-1].value<=y)tail--;
que[tail].value=y,que[tail].pos=x;
tail++;
dp[k*w+b]=que[head].value+k*v;
}
}
}
cout<<dp[V]<<endl;
}
}
这个程序是AC的。需要解释的有两点：1.看上去有3重循环，但是第2层循环只是把数据进行了分组，所以实际最内层循环执行的次数并没有增加；2.前面的分析中k’表示的是先把所有i物品放进背包，然后再取出来的个数，并且也说明了k’实际上就是j/c=a，也就是当前可以放的物品i的个数，因为只有这样才能由k’推算出j，才能把找到的最优解保存在数组dp里。但是，在遍历k’时必须从0到V/c，否则就不能遍历到所有的j，因为这里已经不是用j来求k’，而是用遍历k’代替遍历j了，所以这里k’的循环终值是V-c，而不是m。所以，这里的k’实际就是a，亦即V/c。至于k’实际只能取min(j/c,m)的实质，则体现在队列的长度上，前面已经分析过，多重背包与完全背包的差别就是在队列的长度上，这样是合理的。
四、组合背包
组合背包就是01背包、完全背包、多重背包的组合问题，即，有的物品只有1个，有的物品有无限多个，有的物品有有限多个。显然，多重背包的算法适用于上述各种情况，但是，即便单调队列在求固定长度区单最大值有优势，但是完全背包算法并不需要如此麻烦，01背包也同样不需要。所以，组合背包要更完美一点的话，应该是根据不同情况选择不同的算法。复制一段AC的代码如下，算是对前面几种背包问题的小结吧。
/*DP大作战—组合背包*/
#include <iostream>
#include <cstring>
using namespace std;
int dp[30001];
int V,N;//背包容量、物体种类数
struct {
int value;
int pos;
}que[30001];
void CompletePack(int w,int v){
for(int i=w;i<=V;i++)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
void ZeroOnePack(int w,int v){
for(int i=V; i>=w; i--)
if(dp[i]<dp[i-w]+v)
dp[i]=dp[i-w]+v;
}
void MultiplePack(int w,int v,int m){
for(int r=0;r<w;r++){//枚举余数
int head=0,tail=0;//队列初始化
for(int k=0;k<=(V-r)/w;k++){
int x=k;
int y=dp[k*w+r]-k*v;
while(head<tail&&que[head].pos<k-m)head++;//限制队列长度
while(head<tail&&que[tail-1].value<=y)tail--;
que[tail].value=y,que[tail].pos=x;
tail++;
dp[k*w+r]=que[head].value+k*v;
}
}
}
int main(){
int n,v,w,m;//v物品价值，w物品重量，m物品件数
cin>>n;
while(n--){
memset(dp,0,sizeof(dp));
cin>>V>>N;
for(int i=0;i<N;i++){
cin>>v>>w>>m;
if(m==1)
ZeroOnePack(w,v);
else if(w*m>=V||m==233)
CompletePack(w,v);
else
MultiplePack(w,v,m);
}
cout<<dp[V]<<endl;
}
}