1.背包问题
什么是背包问题？
给定N个物品和一个容量为V的背包，每个物品有体积和价值两种属性，在一些限制条件下，将一些物品装入背包，使得在不超过背包体积的情况下，能够得到的最大价值。根据不同的限制条件，分为不同类型的背包问题。
0-1背包问题
给定N个物品，和一个容量为V的背包，每个物品有2个属性，分别是它的体积v_i(v for volume)，和它的价值w_i (w for weight)，每件物品只能使用一次（0-1背包的特点，每件物品要么用1次（放入背包），要么用0次（不放入背包）），问往背包里放入哪些物品，能够使得物品的总体积不超过背包的容量，且总价值最大。
f(i, j)可以分成两个更小的集合，一种是不包含第i个物品，一种是包含第i个物品
- 不包含第i个物品：就是从物品
1-i中选择，但是不能包含第i个物品的最大价值，换句话就是从物品1-i-1中选择，总体积不超过j的最大价值，即f(i - 1, j) - 包含第i个物品：就是从物品
1-i中选择，但是必须包含第i个物品的最大价值，那么可以认为最开始直接把i塞进背包，此时背包的容量变成了j - vi，价值变成了wi，由于第i个物品已经装进背包了，那么从1-i选就变成了从1-i-1选了，因此此时的最大价值就是f(i - 1, j - vi) + wi
f(i, j)取两种情况的最大值，因此f(i, j)= max(f(i - 1, j), f(i - 1, j - vi) + wi)
AcWing 2. 01背包问题
**实现思路：**求f(i,j)，i从0开始枚举到n件物品，再用j从0开始枚举到最大体积m，由于包含i的集合可能不存在，因此先计算不包含i的集合，即f(i,j)=f(i-1,j)，若当前的状态可以划分包含i的状态，即j>=v[i],那么就计算当前枚举的f(i,j)最终值，即max(f((i-1),j),f(i-1,j-v[i])+w[i]))，当全部枚举结束后，计算的就是f[n][m]，即前n个物品中总体积不超过m的最大价值。
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N],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++)//f[0][j]都默认为0
for(int j=1;j<=m;j++){//f[i][0]都默认为0
f[i][j]=f[i-1][j];//不包含物品i的情况
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);//包含物品i，直接先放进去
}
cout<<f[n][m]<<endl;
return 0;
}
滚动数组优化为一维
将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。
为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，即放前i个物品在体积为j时的最大价值（很多个状态都可以得到），但题目只需要求得最终状态f[n][m]（只要一个状态，不用求那么多状态），因此我们只需要一维的空间来更新状态。
（1）状态f[j]定义：N件物品，背包容量j下的最优解(最大价值)。
（2）注意枚举背包容量j必须从m开始，即逆序遍历处理不同体积。
为什么一维情况下枚举背包容量需要逆序？
在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
**再具体来说：**二维削减为一维，f[j]=max(f[j],f[j-v[i]]+wi)
f[j]从f[j - vi]转移过来，那么这里的f[j - w]是指f[i - 1][j - w]还是f[i][j - w]就尤为重要
-
如果是正序循环，显然
j-vi<j，由于j是递增的，那么在一轮i循环中f[j-vi]必然会在f[j]之前得到，则算到最后f[m]=max(f[m],f[m-vi]+wi)可能这时候的f[m-vi]在本轮循环中已经更新修改过（比如在开头的j处）。就出现了某次更新f[j]的时候就用到了本轮i中的f[j-vi]（就是二维中的f[i][j-vi]，而不是应该用的f[i-1][j-vi]，错误），不是用的上一轮i-1中的f[j-vi]，这就不对了!!!（这里正序实际是完全背包问题的做法） -
如果是逆序循环，就可以完美解决这个问题，j是递减的， 计算
f[j]的时候，用到的f[j - vi]必然还没在本轮更新（还是i-1时候的，旧的好） -
简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。
一维状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] )
不理解？传送门：http://t.csdnimg.cn/Ue73u
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
int v[N],w[N],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++)
//j逆序，到v[i]为止（小于vi就没意义，装不下vi）
for(int j=m;j>=v[i];j--){
//f[j]=f[j];//不包含物品i的情况 改为一维后恒等式 略去
f[j]=max(f[j],f[j-v[i]]+w[i]);//包含物品i 逆序使f[j-v[i]]等效于二维的f[i-1][j-v[i]]
}
cout<<f[m]<<endl;
return 0;
}
完全背包问题
相比0-1背包问题，完全背包问题的各个物品是无限个的，即放入背包的物品i可以不限数量
AcWing 3. 完全背包问题
**实现思路：**和0-1背包问题的区别在状态计算中的集合划分，不是只有0和1，而是可以选k个
朴素做法：与01背包思路相同，只是在集合划分上有所区别，以f[i,j]为例，对其进行下一步划分，考虑以取k个i物品划分集合，若k=0，则相当于f[i-1,j]；若k不等于0，则采取01背包类似的办法，先确定取k个物品i，不影响最终选法的求解，即求f[i-1,j-k*v[i]],再加上k*w[i]，即f[i-1,j-k*v[i]]+k*w[i],不难发现k=0情况可以与之合并，最终就是取从0枚举到k，最终状态转移方程为f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])的最大值，k的最大值可以通过j>=k*v[i]求解。有三重for循环，时间复杂度最差为O(n*m^2)
注意：这里max(f[i][j],f[i-1][j-k*v[i]]+k*w[i])，而不是类似0-1背包那样取max(f[i-1][j],f[i-1][j-k*v[i]]+k*w[i])。因为k=0时，即物品i不取的情况，完全背包方程就为max(f[i][j],f[i-1][j])，实质上就涵盖了f[i-1][j]的情况
#include <iostream>
#include <alforithm>
using namespace std;
const int N=1010;
int w[N],v[N],f[N][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=1;j<=m;j++)
for(int k=0;k*v[i]<=j;k++){
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}**二维优化版：**改为二重循环，降低时间复杂度
像0-1背包那样考虑分成两种情况看待，
第一种情况：从i物品一个都不取开始；
第二种情况：从至少取一份i物品开始，即j-v
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
观察上面两式，括号中对应部分只相差一个w，可得出如下递推关系：
f[i][j]=max( f[i-1][j],f[i,j-v]+w )
所以可以去掉k，即去掉第三重循环
#include <iostream>
#include <alforithm>
using namespace std;
const int N=1010;
int w[N],v[N],f[N][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=1;j<=m;j++){
f[i][j]=f[i-1][j];//不取物品i
if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]);//至少取一份物品i
}
cout<<f[n][m]<<endl;
return 0;
}滚动数组优化
观察可以发现可0-1背包的代码很像，所以可以像0-1背包那样用滚动数组优化。
**区别在于：**第二部分是i-1，还是i，即需要的值是上一轮的i-1还是本轮的i
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包 需要i-1轮的值来更新
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题 需要i轮的值来更新
相比0-1背包，进行滚动优化区别：j是正序遍历处理了（而0-1背包的j是逆序）
详细一点说明：http://t.csdnimg.cn/633A5
#include <iostream>
#include <alforithm>
using namespace std;
const int N=1010;
int w[N],v[N],f[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=v[i];j<=m;j++)//正序遍历j
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}多重背包问题
每件物品的个数是不同的，比如，每件物品的个数是si个。
相比完全背包问题，只是每个物品的个数有了上限，不再是无限
朴素版本：和完全背包问题基本一样，只是k多了个上限限制，用数组s[]表示某个物品的上限。时间复杂度为O(NVS)，会超时
#include <iostream>
#include <alforithm>
using namespace std;
const int N=1010;
int w[N],v[N],f[N][N];
int s[N];//上限
int n,v;
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++) cin>>v[i]>>w[i]>>s[i];
for(int i=1;i<=n;i++)
for(int j=1;j<=v;j++)
for(int k=0;k<=s[i] && k*v[i]<=j;k++){//多一个上限的判断
f[i][j]=max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout<<f[n][v]<<endl;
return 0;
}**二进制优化：**分堆，最后退化为0-1背包问题
-
所谓的二进制优化，我们知道任意一个实数可以由二进制数来表示，也就是可以由2^0~2^k其中一项或几项的和拼凑得到。
比如1,2,4,8,16可以组合表示出0
31中间的任何数，可推导得到**2^1,2^2…2^k可以组合表示02^(k+1)-1中的任何数，即用log(2^k+1)个数就可以表示2^(k+1)个数**，妙啊！。那么对于0
S[i]，本来循环枚举S[i]次，若使用二进制优化，可以只枚举logS[i]次就可以表示出0S[i]范围的所有数，枚举的时间复杂度O(S)降低到S(logS) -
然后对应到多重背包问题：对于物品i限制上限S[i]个，我们对其取多少个进行分堆，每堆的个数为2的倍数，即进行二进制优化，每次就按堆来枚举询问，是否达到最优解，再通俗点说就是原来物品i按每次一个一个询问是否最优，转化为每次一堆一堆（每一堆最多只能用一次，即转化为0-1背包问题了）询问是否最优，效果一样的，因为DP就是找到最优就行。
-
怎么分堆（怎么转为每堆尽量用2的倍数表示）？比如s[i]=200，那么分堆1,2,4,8…64，此时可表示0
127（若分到128，就表示0255，超出200了），还剩下一堆用s[i]-127=73，这样就可以表示0~200中的数。也就是说分堆的时候，先分为k堆，且2^k-1<s[i]，但2^(k+1)-1>s[i]，然后再用一堆放s[i]-(2^k-1)，这样就分为k+1堆，原来s[i]个数转化为k+1个数表示。
经过二进制优化后，时间复杂度为O(NVlogS)，运行不会报超时
注意：这里分堆后，直接覆盖体积数组v[]和价值数组，因为每次询问就是一堆一堆了,v[i]=堆中个数k*v，w[i]=堆中个数k*w
更详细说明：AcWing 5. 二进制优化，它为什么正确，为什么合理，凭什么可以这样分？？ - AcWing
#include <iostream>
#include <algorithm>
using namespace std;
const int N=25000,M=2010;
int n,m;
int w[N],v[N],f[N];
int n,m;
int mian(){
cin>>n>>m;
int cnt=0;//记录堆号 第几堆
for(int i=1;i<=n;i++){
int v,w,s;//当前物品i的体积、价值、上限个数
cin>>v>>w>>s;
int k=1;//记录每堆的个数 递增从1 2 4 8 到剩余的个数不再满足2的倍数 重开一个堆放
while(s>=k){
cnt++;
v[cnt]=k*v;//堆的体积
w[cnt]=k*w;//堆的价值
s-=k;//剩余个数
k*=2;//递增分下一堆
}
if(s>0){//按2的倍数分完还有剩 再开一个堆
cnt++;
v[cnt]=s*v;//堆的体积
w[cnt]=s*w;//堆的价值
}
}
//分好了 各堆只能用一次 0-1背包问题
n=cnt;
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<<f[m];
return 0;
}
分组背包问题
有 N 组物品，每一组中有若干个物品，每一组中至多选择一个。
分组背包问题的思考方式和前面的类似。不同的地方仅仅在于状态转移。
分组背包问题的思考方式和前面的类似。不同的地方仅仅在于状态转移。
01背包的状态转移，是枚举第i个物品选或者不选；
完全背包和多重背包，是枚举第i个物品，选0,1,2,3,4,.... 个，无限个或有上限个
而分组背包，枚举的是第i个分组，选哪一个，或者一个都不选
-
这里的体积数组v和价值数组w就要开成二维，表示某一组的某一个物品
-
与01背包思路一致，集合划分为不包含i组，包含i组第1个物品，包含i组第2个物品，…包含i组第k个物品（k表示第i组的物品数量），…，包含第i组最后一个物品。因此若不包含第i组，则f(i,j)=f(i-1,j),若包含第i组第k个物品，则计算方法类似01背包（只是多了一重循环从i组里面选第k个物品），先除去第i组的第k个物品再进行计算的取法不变
-
分组背包的状态转移方程为：
f[i][j]=max(f[i−1][j],f[i−1][j−v[i][k]]+w[i][k])， 1<k<s[i]。其中 v[i,k] 表示第 i 组中的第 k 个物品的体积，w [ i , k ] 同理。同样可以优化为一维：f[j]=max(f[j],f[j−v[i][k]]+w[i][k])，主要这里更新需要上一组的（和完全背包一样），j要逆序
注意：j逆序枚举的最小值是1，不是0-1背包那样的v[i]，因为i组里面的物品各自的体积都无法提前判断，不知道最小值
#include <iostream>
#include <algorithm>
using namespace std;
const int N =110;
int v[N][N],w[N][N],s[N],f[N];//有些开成二维数组,s表示第i组中的物品数量
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>s[i];
for(int j=1;j<=s[i];j++)
cin>>v[i][j]>>w[i][j];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=1;j--)//逆序枚举体积 这里就和01背包有区别 枚举最小到1
for(int k=1;k<=s[i];k++)
if(j>=v[i][k]) //满足体积还足够放i组第k个
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout<<f[m]<<endl;
return 0;
}