动态规划-----------01背包，完全背包与多重背包

P01: 01背包问题

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。（后面有详细的图解）伪代码如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符，但它却是另一个重要的背包问题P02最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

过程ZeroOnePack，表示处理一件01背包中的物品，两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)

for v=V..cost

f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了，避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了，就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1]，这是显然的。

有了这个过程以后，01背包问题的伪代码就可以这样写：

for i=1..N

ZeroOnePack(c[i],w[i]);

初始化的细节问题

我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题，后面也就不再对进行状态转移之前的初始化进行讲解。

小结

01背包问题是最基本的背包问题，它包含了背包问题中设计状态、方程的最基本思想，另外，别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法，状态转移方程的意义，以及最后怎样优化的空间复杂度。

二维数组代码的写法

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 int dp[1005][1005];  
 4 int weight[1005];  
 5 int value[1005];  
 6 int main()  
 7 {  
 8     int n,m;  
 9     cin>>m>>n;  
10     memset(dp,0,sizeof(dp));//数组清空,其实同时就把边界给做了清理  
11     for(int i=1; i<=n; i++)  
12         cin>>weight[i]>>value[i];  
13     //从1开始有讲究的因为涉及到dp[i-1][j],从0开始会越界  
14     for(int i=1; i<=n; i++)//判断每个物品能否放进  
15     {  
16         for(int j=0; j<=m; j++)//对每个状态进行判断  
17         //这边两重for都可以倒着写，只是需要处理最边界的情况，滚动数组不一样  
18         {  
19             if(j>=weight[i])//能放进  
20                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);  
21   
22             else dp[i][j]=dp[i-1][j];//不能放进  
23         }  
24     }  
25     cout<<dp[n][m]<<endl;  
26     return 0;  
27 }

这个数组开销还是很大的，因为是二维的，万一哪个数据一大，分分钟内存超限，所以我们要进行优化。

3、空间优化

　　空间优化，每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；

　　因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；

　　并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否者前一次循环保存下来的值将会被修改，从而造成错误。

　　同样以上述例子中i=3时来说明，有:

　　　　1) i=3，j=8，w(3)=4，v(3)=5，有j>w(3)，则B(8)=max｛B(8)，B(8-w(3))+v(3)｝=max｛B(8)，B(4)+5｝=max｛7，4+5｝=9；

　　　　2) j- -即j=7，有j>w(3)，则B(7)=max｛B(7)，B(7-w(3))+v(3)｝=max｛B(7)，B(3)+5｝=max｛7，4+5｝=9；

　　　　3) j- -即j=6，有j>w(3)，则B(6)=max｛B(6)，B(6-w(3))+v(3)｝=max｛B(6)，B(2)+5｝=max｛7，3+5｝=8；

　　　　4) j- -即j=5，有j>w(3)，则B(5)=max｛B(5)，B(5-w(3))+v(3)｝=max｛B(5)，B(1)+5｝=max｛7，0+5｝=7；

　　　　5) j- -即j=4，有j＝w(3)，则B(4)=max｛B(4)，B(4-w(3))+v(3)｝=max｛B(4)，B(0)+5｝=max｛4，0+5｝=5；

　　　　6) j- -即j=3，有j<w(3)，继续访问数组会出现越界，所以本轮操作停止，B(0)到B(3)的值保留上轮循环（i=2时）的值不变，进入下一轮循环i++；

　　如果j不逆序而采用正序j=0...capacity，如上图所示，当j=8时应该有B(8)=B(8-w(3))+v(3)=B(4)+5，然而此时的B(4)已经在j=4的时候被修改过了，原来的B(4)=4，现在B(4)=5，所以计算得出B(8)=5+5=10，显然这于正确答案不符合；所以该一维数组后面的值需要前面的值进行运算再改动，如果正序便利，则前面的值将有可能被修改掉从而造成后面数据的错误；相反如果逆序遍历，先修改后面的数据再修改前面的数据，此种情况就不会出错了；

这里用到的一维数组就是传说中的---------------滚动数组！！！

什么是滚动数组。

说白了二维数组只是把每个物品都跑一遍，然后到最后一个物品的时候输出答案，那么过程值只是计算的时候用一次，我没必要存下来。所以用一个数组去滚动存储，然后用后一个状态的值去覆盖前面一个状态。然后形象的叫它：滚动数组

用滚动数组求01背包的最重要的一点就是：第二层循环要逆序！！！如上图图解，代码如下：

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 int dp[1005];//滚动数组的写法，省下空间省不去时间  
 4 int weight[1005];  
 5 int value[1005];  
 6 int main()  
 7 {  
 8     int n,m;  
 9     cin>>m>>n;  
10     memset(dp,0,sizeof(dp));  
11     for(int i=1; i<=n; i++)  
12         cin>>weight[i]>>value[i];  
13     for(int i=1; i<=n; i++)//对每个数判断，可反  
14     {  
15         for(int j=m; j>=weight[i]; j--)//这里这个循环定死，不能反,反了就是完全背包  
16         {  
17             dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);//其实不断在判断最优解，一层一层的  
18         }  
19     }  
20     cout<<dp[m]<<endl;  
21     return 0;  
22 }

P02: 完全背包问题

题目有N种物品和一个容量为V的背包。第i种物品有若干件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本思路:

这个问题和我们刚解决的01背包问题很像,不同的是该问题中的物品每一件有若干件,而01背包中的每一件物品只有一件.

其中F[i-1][j-K*C[i]]+K*W[i]表示前i-1种物品中选取若干件物品放入剩余空间为j-K*C[i]的背包中所能得到的最大价值加上k件第i种物品；

设物品种数为N，背包容量为V，第i种物品体积为C[i]，第i种物品价值为W[i]。

与01背包相同，完全背包也需要求出NV个状态F[i][j]。但是完全背包求F[i][j]时需要对k分别取0,…，j/C[i]求最大F[i][j]值,耗时为j/C[i]。那么总的时间复杂度为O(NV∑(j/C[i]))，代码如下：

 1 #include<bits/stdc++.h>  
 2 using namespace std;   
 3 const int maxn=555;  
 4 int dp[maxn][111111];  
 5 int need[maxn],value[maxn];  
 6 int n,m;  
 7 int main()  
 8 {  
 9     int i,j,k;  
10     while(~scanf("%d %d",&n,&m))  
11     {  
12         memset(dp,0,sizeof(dp));  
13         for(i=1;i<=n;i++)  
14             scanf("%d %d",&need[i],&value[i]);   
15         for(i=1;i<=n;i++)  
16         {  
17             for(j=0;j<=m;j++)  
18             {  
19                 for(k=0;k*need[i]<=j;k++)      
20                     dp[i][j]=max(dp[i][j],dp[i-1][j-k*need[i]]+k*value[i]);  
21             }  
22         }  
23         printf("%d
",dp[n][m]);  
24     }  
25     return 0;  
26 }

优化空间复杂度为O（V）

和01背包问题一样，完全背包也可以用一维数组来保存数据。算法样式和01背包的很相似，唯一不同的是对V遍历时变为正序，而01背包为逆序

。01背包中逆序是因为F[i][]只和F[i-1][]有关，且第i件的物品加入不会对F[i-1][]状态造成影响。而完全背包则考虑的是第i种物品的出现的问题，

第i种物品一旦出现它势必应该对第i种物品还没出现的各状态造成影响。也就是说，原来没有第i种物品的情况下可能有一个最优解，现在第i种物品

出现了，而它的加入有可能得到更优解，所以之前的状态需要进行改变，故需要正序。优化后的代码为：

 1 [cpp] view plain copy
 2 #include<bits/stdc++.h>  
 3 using namespace std;   
 4 const int maxn=555;  
 5 int dp[111111];  
 6 int need[maxn],value[maxn];  
 7 int n,m;  
 8 int main()  
 9 {  
10     int i,j,k;  
11     while(~scanf("%d %d",&n,&m))  
12     {  
13         memset(dp,0,sizeof(dp));  
14         for(i=1;i<=n;i++)  
15             scanf("%d %d",&need[i],&value[i]);   
16         for(i=1;i<=n;i++)  
17         {  
18             for(j=need[i];j<=m;j++)  
19             {  
20                 if(j>=need[i])  
21                   dp[j]=max(dp[j],dp[j-need[i]]+value[i]);  
22                 }  
23         }  
24         printf("%d
",dp[m]);  
25     }  
26     return 0;  
27 }

两者区别：

1.01背包：有n种物品与承重为m的背包。每种物品只有一件，每个物品都有对应的重量weight[i]与价值value[i]，求解如何装包使得价值最大。

2.完全背包：有n种物品与承重为m的背包。每种物品有无限多件，每个物品都有对应的重量weight[i]与价值value[i]，求解如何装包使得价值最大。

P03: 多重背包问题

题目

有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

基本算法

这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}

复杂度是O(V*Σn[i])。用完全背包思想实现的代码如下：

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 const int N = 1005;  
 4   
 5 int dp[N];  
 6 int c[N],w[N],num[N];  
 7 int n,m;  
 8   
 9 void ZeroOne_Pack(int cost,int weight,int n)//吧01背包封装成函数  
10 {  
11     for(int i=n; i>=cost; i--)  
12         dp[i] = max(dp[i],dp[i-cost] + weight);  
13 }  
14   
15 void Complete_Pack(int cost,int weight,int n)//把完全背包封装成函数  
16 {  
17     for(int i=cost; i<=n; i++)  
18         dp[i] = max(dp[i],dp[i-cost] + weight);  
19 }  
20   
21 int Multi_Pack(int c[],int w[],int num[],int n,int m)//多重背包  
22 {  
23     memset(dp,0,sizeof(dp));  
24     for(int i=1; i<=n; i++)//遍历每种物品  
25     {  
26         if(num[i]*c[i] > m)  
27             Complete_Pack(c[i],w[i],m);  
28             //如果全装进去已经超了重量，相当于这个物品就是无限的  
29             //因为是取不光的。那么就用完全背包去套  
30         else  
31         {  
32             int k = 1;  
33             //取得光的话，去遍历每种取法  
34             //这里用到是二进制思想，降低了复杂度  
35             //为什么呢，因为他取的1,2,4,8...与余数个该物品，打包成一个大型的该物品  
36             //这样足够凑出了从0-k个该物品取法  
37             //把复杂度从k变成了logk  
38             //如k=11，则有1,2,4,4，足够凑出0-11个该物品的取法  
39             while(k < num[i])  
40             {  
41                 ZeroOne_Pack(k*c[i],k*w[i],m);  
42                 num[i] -= k;  
43                 k <<= 1;  
44             }  
45             ZeroOne_Pack(num[i]*c[i],num[i]*w[i],m);  
46         }  
47     }  
48     return dp[m];  
49 }  
50   
51 int main()  
52 {  
53     int t;  
54     cin>>t;  
55     while(t--)  
56     {  
57         cin>>m>>n;  
58         for(int i=1; i<=n; i++)  
59             cin>>c[i]>>w[i]>>num[i];  
60         cout<<Multi_Pack(c,w,num,n,m)<<endl;  
61     }  
62     return 0;  
63 }

另一种好想好写的基本方法是转化为01背包求解：把第i种物品换成n[i]件01背包中的物品，则得到了物品数为Σn[i]的01背包问题，直接求解，复杂度仍然是O(V*Σn[i])。

首先这种可以把物品拆开，把相同的num[i]件物品看成价值跟重量相同的num[i]件不同的物品，那么！！是不是就转化成了一个规模稍微大一点的01背包了。对不对？

 1 #include<bits/stdc++.h>  
 2 using namespace std;  
 3 int dp[1005];  
 4 int weight[1005],value[1005],num[1005];  
 5 int main()  
 6 {  
 7     int n,m;  
 8     cin>>n>>m;  
 9     memset(dp,0,sizeof(dp));  
10     for(int i=1; i<=n; i++)  
11         cin>>weight[i]>>value[i]>>num[i];  
12           
13     for(int i=1; i<=n; i++)//每种物品  
14           
15         for(int k=0; k<num[i]; k++)//其实就是把这类物品展开，调用num[i]次01背包代码  
16           
17             for(int j=m; j>=weight[i]; j--)//正常的01背包代码  
18               
19                 dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);  
20       
21     cout<<dp[m]<<endl;  
22     return 0;  
23 }

但是我们期望将它转化为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的四件物品。

分成的这几件物品的系数和为n[i]，表明不可能取多于n[i]件的第i种物品。另外这种方法也能保证对于0..n[i]间的每一个整数，均可以用若干个系数的和表示，这个证明可以分0..2^k-1和2^k..n[i]两段来分别讨论得出，并不难，希望你自己思考尝试一下。

这样就将第i种物品分成了O(log n[i])种物品，将原问题转化为了复杂度为O(V*Σlog n[i])的01背包问题，是很大的改进。

下面给出O(log amount)时间处理一件多重背包中物品的过程，其中amount表示物品的数量：

procedure MultiplePack(cost,weight,amount)

if cost*amount>=V

CompletePack(cost,weight)

return

integer k=1

while k<num

ZeroOnePack(k*cost,k*weight)

amount=amount-k

k=k*2