背包问题，本质上就是给几种物品，每个物品有体积有价值，可能有个数限制
有一个容量有限的背包，在背包能装下的前提下，能装的最大价值是多少
背包问题一般分为这几种：
01背包：每件物品只有一个
完全背包：每件物品有无限个
多重背包：每件物品有Si个（有限个）
分组背包：所有物品被分为多个组，每一组最多只能选一个物品
动态规划主要要点：
状态表示：如何表示这样的选法的值，以及要考虑多少维状态
状态计算：如何计算每一个状态
DP优化：一般来说是对dp方程或代码进行等价变形
从集合的角度理解dp（所有选法的集合）
状态表示：
1.这样的状态表示怎样的集合
2.这样的状态的值，是这样的集合的某种属性（Max,Min,数量）
集合表示状态：
1.表示所有选法
2.(1)只从前i个物品中选 (2)总体积<=j
满足这两个条件的所有选法的集合就是f[i][j]表示的集合
属性是f[i][j]这个集合中价值的最大值
属性计算（f[i][j]可以被如何计算出来）：
如果把所有状态计算出来之后，我们的答案应该是f[n][v]，f[n][v]所表示的集合就是n个物品中总体积小于v的最大价值的选法，而它的值就是最大价值
状态计算：
一般对应集合的划分
例如01背包问题
把f[i][j]这样的集合分类
分为：1.所有不包含第i个物品的选法 2.所有包含第i个物品的选法
一般划分有两个原则：1.不重复（某个元素只会属于一个集合）
2.不漏（某一个元素不能不属于任何一个集合）
不重复不一定满足，比如求最值时，可以重复比较
对于左半边，为从1~i中选，但是不选i，体积<=j的选法，既然不选第i个物品，那么
可以等价为 从1~(i-1)中选，体积<=j的选法的集合，即f[i-1][j]表示的集合
而f[i-1][j]的值就是从1~(i-1)中选的最大价值
那么左边的最大值就是f[i-1][j]
对于右半边，为从1~i中选，且一定选i，体积<=j的选法，这里没法自然像左边那样得到
需要绕一下：可以先把1~i中的所有选法的第i个物品都去除掉，不考虑有第i个物品，这样是不影响最大值的选择的，最大值还是那样的选法
那么这样就等价为从1~(i-1)中选，体积<=j-Vi的选法的集合，即f[i-1][j-Vi]的集合
f[i-1][j-Vi]的值就是这些选法的最大值，但它还不是我们的右半边的最大值
直接加上Wi就是我们的右半边的最大值了
那么右边的最大值就是f[i-1][j-Vi]+Wi
那么整个f[i][j]的最大值就是这左右两边两个集合的最大值
即f[i][j]=max(f[i-1][j] , f[i-1][j-Vi]+Wi )
而这就是状态转移方程,所有的选法状态之间都是靠这个方程转移的
但是右半边可能不存在，即空集
当j<Vi时，定义上需要选择第i个物品，但是体积不够选不了第i个物品
故这种情况下，不存在选了第i个物品的选法，为空集
但是左边一定存在
01背包：
https://www.acwing.com/problem/content/submission/2/
//由于f[i][j]的状态表示
//f[0][0~m]应该都是0，表示前0个物品的选择，不超过m的体积，0个物品即一个都没选，故价值为0
//由于f[i][j]定义为全局变量，默认为0，就不用去再设置了
#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1005;
int v[N],w[N],f[N][N];
int a,b;
int main()
{
cin >> a >> b;
for(int i=1;i<=a;i++)
scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=a;i++)
for(int j=1;j<=b;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
cout << f[a][b] << endl;
return 0;
}由于每一次循环我们的状态计算只会用到前一层的状态,而再往前的状态不会用到
因此可以用滚动数组来优化
而状态转移方程的j总是 <= j的,无论是j,还是j-Vi,都小于j
因此具有单调性,可以考虑优化为1维
对原来的方程进行等价变化
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int N =1005;
int n,m;
int w[N],v[N];
int f[N];
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]);
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] << endl;
return 0;
}
完全背包:
https://www.acwing.com/problem/content/3/
同样的用集合角度分析
状态表示和01背包基本一样
但是状态计算-集合的划分不一样
由于完全背包有无限个物品
可以考虑如图01背包一样,第i个物品选几个,来划分组(子集)
第i个物品选多少个,来划分
这样就把f[i][j]划分为k个子集了
再去看每一个子集如何计算
选0个,如同01背包一样,为:f[i-1][j]
通解,第i个物品选k个这样的集合计算,需要绕一下
1.去掉k个物品i,不考虑第i个物品
2.再去求Max,即f[i-1][j-k*Vi]表示的集合的最大值
3.再加回来k个物品i
即f[i-1][j-k*Vi]+k*Wi
而选0个是通解的k为0的情况
综合来看,就是
f[i][j]=f[i-1][j-k*Vi] + k*Wi
但是这样的状态转移方程复杂度较高
需要枚举i,j的状态,还需要枚举物品选多少个,最多为k*Vi<=j
需要用到三重循环
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int 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++)//枚举物品状态
for(int j=0;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;
}优化状态转移方程
展开:
对于第i个物品,f[i][j]=max(一个都不选,选一个,选两个...选k个),取这些情况
对比一下f[i][j-v]
观察f[i][j-v],发现与f[i][j]对应的项只少一个w
那么f[i][j]的最大值就是f[i][j-v]的最大值,再加上一个w
即有 
那么就优化成O(N^2)了
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int 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++)//枚举物品
for(int j=0;j<=m;j++)//枚举空间
{
f[i][j]=f[i-1][j];
//空间足够
if(j>=v[i])f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
cout << f[n][m] << endl;
return 0;
}再用滚动数组优化为1维
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int v[N],w[N];
int 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++)//枚举物品
for(int j=v[i];j<=m;j++)//枚举空间
{
f[j]=max(f[j],f[j-v[i]]+w[i]);//不需要倒序,符合原来的状态转移方程
}
cout << f[m] << endl;
return 0;
}
多重背包
https://www.acwing.com/problem/content/4/
同样的是从集合角度
状态计算就是集合的划分
也是根据第i个物品选多少个,来划分f[i][j]类
如同完全背包
状态转移方程为:f[i][j] = max(f[i-1][j-k*v[i]] + k*w[i]) ; k=0,1,2,3...,s[i]
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n,m;
int f[N][N];
int w[N],v[N];
int s[N];
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)cin >> v[i] >> w[i] >> s[i];
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k*v[i]<=j && k<=s[i]; 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;
}优化:
分析转移方程 
对比f[i][j-v]
发现会多出一项f[i-1][j-(s+1)v]+sw
由于这一项的存在,导致我们无法直接使用完全背包的优化方式求最大值
这里采用二进制的优化方式
即将2的整数次幂分为一组,即选1个,2个,4个,8个,...512个第i个物品,
通过选择这些组,可以凑出来选择任意个第i个物品的个数(倍增思想)
每一组可以看成是01背包的问题,每个组只能选一次
枚举每一个组选与不选,就可以拼凑所有的方案
例如s=200
那么 1, 2, 4, 8, 16, 32, 64
最多只到64,因为若到128,那么最多能凑成255个物品
但是我们的实际没有那么大,最多只能到200
从1+到64,是127,还差73
那么这些组就可以表示0~127之间任何一个数
那么再加个73就可以凑出来0~200的任何一个数了
一般来看,把它的规律抽象出来:
有一个s
1 , 2 , 4 ,8 ,...2^k,再加上个 c , c<2^(k+1)
显然用倍增思想可以知道可以凑出来0 ~ 2^(k+1)-1 的任何一个数
加上c后就是 c~2^(k+1)-1+c
即c~s
这两个区间可以证明并起来是连续的,即0~s,任何一种拼法都能被凑出来
即给定第i个物品个数为Si个,那么就把Si拆分成logSi个,再对这logSi个新物品做一遍01背包问题就ok了
原来的时间复杂度是N*V*S
现在是N*V*logS
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 25000,M=2010;//2000个物品,log2000=11,那么最大空间22000
int n,m,cnt;
int v[N],w[N];
int f[N];
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin >> a >> b >> s;//体积,价值,个数
int k=1;
while(k<=s)//二进制优化
{
cnt++;
v[cnt]=a*k;
w[cnt]=b*k;
s-=k;
k*=2;
}
if(s>0)//此时s为剩余的c
{
cnt++;
v[cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;
//一维01背包
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] << endl;
return 0;
}
分组背包问题:
https://www.acwing.com/problem/content/9/
同样的从集合的角度出发
状态计算:
枚举第i组物品选哪个,或者不选
第一种情况即第i组物品一个都不选,等价于从前i-1个物品中选,体积<=j,即f[i-1][j]
对于通解,从第i个组选第k个物品,其集合为f[i-1][j-v[i][k] ] +w[i][k],v[i][k]为第i组物品的第k个物品,w[i][k]同理
同样的,分组背包可以优化为1维
1.转移方程用的是上一层状态转移的话,就需要从大到小枚举体积(从大到小可以保证用的还是上一层的状态,即第i-1次循环时更新的状态,这个要点主要对我来说是要明白二重循环的顺序,它是先枚举完第i-1层的所有j,即f[i-1][0~m]全都被计算过了,再去计算第i层,而j又大于j-v[i][k],因此正序的话会先计算小的体积,即f[i][j-v[i][k]),那么此时如果是一维的话就和原式不符了,倒序就会先计算大的体积,f[j-v[i][k]]此时是没有在第i层更新的,它上一次更新是在i-1层的时候,那么就符合原式了)
2.而如果是本层状态转移过来的话,就从小到大枚举体积
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 110;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N];
int main()
{
cin >> n >> m;
for(int i=1;i<=n;i++)//组
{
cin >> s[i];
for(int j=0;j<s[i];j++)
cin >> v[i][j] >> w[i][j];
}
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)//倒序
for(int k=0;k<s[i];k++)
if(v[i][k]<=j)//可以放
f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
cout << f[m] << endl;
return 0;
}