01背包
一个背包中容量为V，现在有N个物品，每个物品的第i个 物品体积为weight[i]，价值为value[i]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？这是01背包的最基础最根本的问题。01代表的意思是该物品取或者不取。顺便提一下各种背包之间的区别，完全背包每种物品的数目是无限种，多重背包的每种物品数目是有限中。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把这个过程理解为当取第i件物品是，价值为f[i-1][v-c[i]]+w[i]；
当不取第i件物品时，价值为f[i-1][v];
作图便是如下：内层循环为v从1到V，外层循环是n从1到N；
测试代码：
1 #include<iostream> 2 using namespace std; 3 #define V 1500 4 unsigned int f[10][V];//全局变量，自动初始化为0 5 unsigned int weight[10]; 6 unsigned int value[10]; 7 #define max(x,y) (x)>(y)?(x):(y) 8 int main() 9 { 10 11 int N,M; 12 cin>>N;//物品个数 13 cin>>M;//背包容量 14 for (int i=1;i<=N; i++) 15 { 16 cin>>weight[i]>>value[i]; 17 } 18 for (int i=1; i<=N; i++) 19 for (int j=1; j<=M; j++) 20 { 21 if (weight[i]<=j) 22 { 23 f[i][j]=max(f[i-1][j],f[i-1][j-weight[i]]+value[i]); 24 } 25 else 26 f[i][j]=f[i-1][j]; 27 } 28 29 cout<<f[N][M]<<endl;//输出最优解 30 31 }
01背包内存优化：可将状态转移方程中二维数组转化为一维数组，状态方程为：
f[j]=max{f[j],f[j-v[i]]+val[i]}
此时需要保证f[j-v[i]]是上一层状态的，即假如左边的f[j]是前i件物品，那么需要保证f[j-v[i]]是前i-1件物品。那么内层循环必须是逆序，举个例子，加入是顺序遍历的话：
物品号 重量(c) 价值(w)
i=1 4 5
i=2 7 9
i=3 5 6
f[v]=max{ f[v],f[v-c[i]]+w[i] }
如果v是顺序递增 i=1时，v=4~10 （因为v要至少大于等于c[i]嘛 不然减出个负数没意义）
原先的: f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=0 f[5]=0 f[6]=0 f[7]=0 f[8]=0 f[9]=0 f[10]=0
--------------------------- i=1 -------------------------------- 后来的： f[0]=0 f[1]=0 f[2]=0 f[3]=0 f[4]=5 f[5]=5 f[6]=5 f[7]=5 f[8]=0 f[9]=0 f[10]=0
v=4:
f[4]=max{f[4],f[0]+5} max{0,5}=5 f[4]=5
v=5:
f[5]=max{f[5],f[1]+5} max{0,5}=5 f[5]=5
v=6:
f[6]=max{f[6],f[2]+5} max{0,5}=5 f[6]=5
v=7:
f[7]=max{f[7],f[3]+5} max{0,5}=5 f[7]=5
v=8:
f[8]=max{f[8],f[4]+5} max{0,10}=10 f[8]=10 (这里显然不对,这时i=1，只能放一件物品,然而没有一个物品的价值为10的 )
v=9:
f[9]=max{f[9],f[5]+5} max(0,10}=10 f[9]=10
v=10:
f[10]=max{f[10],f[6]+5} max{0,10}=10 f[10]=10
所以必须是逆序：
1 for(i=1;i<=n;i++) 2 for(j=v;j>=v[i];j--) 3 { 4 f[j]=max{f[j],f[j-v[i]]+val[i]}; 5 }
注：此处没有对j<v[i]做分类讨论是因为当j<v[i]时默认了f[j]等于上一层的f[j]，即保持不变。
多重背包
已知一个容量为v的背包和N件物品，第i件物品最多有num[i]件，没见物品的重量是weight[i],收益是cost[i];
物品个数N = 3，背包容量为V = 8，则背包可以装下的最大价值为64.
基本思路：直接扩展01背包
状态转移方程：
f[i][j]=max{f[i][j],f[i-1][j-k*weight[i]+k*cost[i]};其中0<=k&&k<=j/weight[i],这是与01背包不同之处，边界条件。
注：此处为f[i][v]而不是f[i-1][v]，f[i][v]就相当于第i种物品中(m1,m2,m3,m4...)的上一层，上次没注意然后就wa了。
直接抄了网上的代码，如下：
1 #include <iostream> 2 using namespace std; 3 const int N = 3;//物品个数 4 const int V = 8;//背包容量 5 int Weight[N + 1] = {0,1,2,2}; 6 int Value[N + 1] = {0,6,10,20}; 7 int Num[N + 1] = {0,10,5,2}; 8 int f[N + 1][V + 1] = {0}; 9 /* 10 f[i][v]:表示把前i件物品放入容量为v的背包中获得的最大收益。 11 f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Weight[i]] + K * Value[i]);其中1 <= k <= min(Num[i],V/Weight[i]) 12 //初始化 13 f[i][0] = 0; 14 f[0][v] = 0; 15 */ 16 int MultiKnapsack() 17 { 18 int nCount = 0; 19 //初始化 20 for (int i = 0;i <= N;i++) 21 { 22 f[i][0] = 0; 23 } 24 for (int v = 0;v <= V;v++) 25 { 26 f[0][v] = 0; 27 } 28 //递推 29 for (int i = 1;i <= N;i++) 30 { 31 for (int v = Weight[i];v <= V;v++) 32 { 33 f[i][v] = 0; 34 nCount = min(Num[i],v/Weight[i]);//是当前背包容量v，而不是背包的总容量 35 for (int k = 0;k <= nCount;k++) 36 { 37 f[i][v] = max(f[i][v],f[i - 1][v - k * Weight[i]] + k * Value[i]); 38 } 39 } 40 } 41 return f[N][V]; 42 } 43 int main() 44 { 45 cout<<MultiKnapsack()<<endl; 46 system("pause"); 47 return 1; 48 }
一维多重背包(选择01背包思想)，将相同的物品看作不同的来处理，然后选择取或者不取，但复杂度比较高
1 for(i=1;i<=n;i++) 2 { 3 for(j=0;j<=b[i];j++) 4 { 5 for(m=k;m>=a[i]*j;m--) 6 { 7 if(f[m]<(f[m-j*w[i]]+j*val[i])) 8 f[m]=f[m-j*w[i]]+j*val[i]; 9 } 10 } 11 }
多重背包二进制优化模板：(思考在这里)
1 for(i=1;i<=n;i++) 2 { 3 p=0; 4 g=0; 5 while(b[i]>g) 6 { 7 for(j=k;j>=a[i]*g;j--) 8 { 9 f[j]=max(f[j],f[j-w[i]*g]+val[i]*g); 10 } 11 b[i]-=g; 12 g=pow(2,p); 13 p++; 14 } 15 for(j=k;j>=w[i]*b[i];--j) 16 { 17 f[j]=max(f[j],f[j-w[i]*b[i]]+val[i]*b[i]); 18 } 19 }
完全背包
完全背包只是每种物品的数量被放到了无限大，此时相对与多重背包变化的只是范围。
有一个容量为V的背包和N件物品，第i件物品的重量是weight[i]，收益是cost[i]。每种物品都有无限件，能放多少就放多少。在不超过背包容量的情况下，最多能获得多少价值或收益？
1.基本思路：直接扩展01背包
状态转移方程：
f[i][v] = max(f[i ][v],f[i][v - K * weight[i]] + K * Value[i]); 其中 0<= K * weight[i] <= j,(v指此时背包容量，不是总容量)
1 #include <iostream> 2 #include <assert.h> 3 using namespace std; 4 /* 5 f[i][v]:前i件物品放入背包容量为v的背包获得的最大收益 6 7 f[i][v] = max(f[i - 1][v],f[i - 1][v - k * Wi] + k * Vi,其中 1<=k<= v/Wi) 8 9 边界条件 10 f[0][v] = 0; 11 f[i][0] = 0; 12 */ 13 14 const int N = 3; 15 const int V = 5; 16 int weight[N + 1] = {0,3,2,2}; 17 int Value[N + 1] = {0,5,10,20}; 18 19 int f[N + 1][V + 1] = {0}; 20 21 int Completeknapsack() 22 { 23 //边界条件 24 for (int i = 0;i <= N;i++) 25 { 26 f[i][0] = 0; 27 } 28 for (int v = 0;v <= V;v++) 29 { 30 f[0][v] = 0; 31 } 32 //递推 33 for (int i = 1;i <= N;i++) 34 { 35 for (int v = 1;v <= V;v++) 36 { 37 f[i][v] = 0; 38 int nCount = v / weight[i]; 39 for (int k = 0;k <= nCount;k++) 40 { 41 f[i][v] = max(f[i][v],f[i - 1][v - k * weight[i]] + k * Value[i]); 42 } 43 } 44 } 45 return f[N][V]; 46 } 47 48 int main() 49 { 50 cout<<Completeknapsack()<<endl; return 1; 53 }
内存压缩：可以接着01背包内存压缩的为什么内层循环方向分析，一维01背包内层循环反向max中的f[j]，f[j-w[i]]+val[i]是上一层的，而在完全背包中内层循环是从w[i]到v正向，刷新的是当前层的状态，看不懂可以再次分析上面的例子
1 for(i=1;i<=n;i++) 2 { 3 for(j=w[i];j<=v;j++) 4 { 5 f[j]=max(f[j],f[j-w[i]]+val[i]); 6 } 7 }
2.直接利用多重背包
完全背包的物品可以取无限件，根据背包的总容量V和第i件物品的总重量Weight[i],可知，背包中最多装入V/Weight[i](向下取整)件该物品。因此可以直接改变第i件物品的总个数，使之达到V/Weight[i](向下取整)件，之后直接利用01背包的思路进行操作即可。
举例：物品个数N = 3，背包容量为V = 5。
拆分之前的物品序列：
拆分之后的物品序列：
根据上述思想：在背包的最大容量（5）中，最多可以装入1件物品一，因此不用扩展物品一。最多可以装入2件物品二，因此可以扩展一件物品二。同理，可以扩展一件物品三。
背包问题九讲：http://love-oriented.com/pack/Index.html
背包之01背包、完全背包、多重背包详解 ：http://www.wutianqi.com/?p=539
背包问题九讲笔记_01背包：http://blog.csdn.net/insistgogo/article/details/8579597
背包问题九讲笔记_完全背包：http://blog.csdn.net/insistgogo/article/details/11081025
背包问题九讲笔记_多重背包：http://blog.csdn.net/insistgogo/article/details/11176693
01背包、完全背包、多重背包：http://blog.csdn.net/wzy_1988/article/details/12260343