背包
背包指一类在有限制的条件下选取一些物品使物品总价值最大的问题。
每个物品有其价值 v[i] 代价 w[i] ，可承受的最大代价为 W。
背包问题的解题方法大致就是考虑选与不选两种情况那种最优。
01背包
01背包顾名思义就是每种物品*选（1）不选（0）两种情况。
状态设置：
f[i][j]表示在前i个物品中花了j的代价所取得的最大价值。
转移方程：
f[i-1][j]表示不取第i个物品。
f[i-1][j-w[i]]+v[i]表示取第i个物品。
显然 f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i])
标程（P1048采药）:
完全的模板，没什么好说的。
#include<bits/stdc++.h>
using namespace std;
int W,n,m,v[1001],w[1001],f[1001][1001];
int main()
{
cin>>W>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=W;j++)
{
if(j<w[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
}
}
cout<<f[n][W];
return 0;
}
训练题：P1507 NASA的食物计划
完全背包
大致与01背包一样，只是每件物品有无限个。
转移方程
在01背包中i号物品的情况由i-1转移而来，但在完全背包中i就由i转移。(有点不好理解看看代码就好了)
j<w[i]时
01背包 f[i][j]=0
完全背包 f[i][j]=0
j=w[i]时
01背包 f[i][j]=max(f[i-1][j],v[i])
完全背包 f[i][j]=max(f[i-1][j],v[i])
j>w[i]时
01背包 f[i][j]=max(f[i-1][j],f[i-1][j]+v[i])这使得在计算f[i][j]时最多只会加一次v[i]（f[i-1][j]里没有v[i]) 。
完全背包 f[i][j]=max(f[i-1][j],f[i][j]+v[i]) 由于f[i][j]里可能已经加过v[i]了，所以计算f[i][j]时可能会加多次v[i]。
f[i-1][j]表示不取第i个物品。
f[i][j-w[i]]+v[i]表示取第i个物品。
f[i][j]=max(f[i-1][j],f[i][j-w[i]]+v[i])
标程：
#include<bits/stdc++.h>
using namespace std;
int W,n,m,v[1001],w[1001],f[1001][1001];
int main()
{
cin>>W>>n;
for(int i=1;i<=n;i++)
cin>>w[i]>>v[i];
for(int i=1;i<=n;i++)
{
for(int j=0;j<=W;j++)
{
if(j<w[i])
f[i][j]=f[i-1][j];
else
f[i][j]=max(f[i][j-w[i]]+v[i],f[i-1][j]);
}/// 就这里有点区别
}
cout<<f[n][W];
return 0;
}例题（P1616疯狂的采药）
这也是一道模板题然而上面的代码只能得30分，一看数据范围 n<=1e4 m<=1e7,如开f[1e4][1e7]那空间就炸了。所以要A掉这题需要更多优化技巧。
压维优化
不难发现，以上的所有转移都是由f[i-1]到f[i]的转移，f[i-2]以及之前的被浪费掉了，所以我们可以用一维数组替代二唯数组来优化空间。
///完全背包
#include<bits/stdc++.h> using namespace std; long long t,m,f[10000005],w[10005],v[10005]; int main() { cin>>t>>m; for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; for(int i=1;i<=m;i++) for(int j=w[i];j<=t;j++)///j由小往大 f[j]=max(f[j],f[j-w[i]]+v[i]); cout<<f[t]; return 0; }
///01背包
#include<bits/stdc++.h> using namespace std; long long t,m,f[10000005],w[10005],v[10005]; int main() { cin>>t>>m; for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; for(int i=1;i<=m;i++) for(int j=1;j<=w[i];j++)///j由大往小 f[j]=max(f[j],f[j-w[i]]+v[i]); cout<<f[t]; return 0; }
学会了这样的写法二维的写法就可以被舍弃了，一维完全可以替代二维。
多重背包
如果每件物品有有限个呢？显然可以把m个物品拆为m个1个的物品，但这样的复杂度往往无法接受。
这里可以使用二进制拆分：
如10拆成 1 2 4 3
16拆成 1 2 4 8
标程：P1776 宝物筛选
#include<bits/stdc++.h>
using namespace std;
int n,w,v[1005],u[1005],_m[1005],_v[20005],_u[20005],f[5000005],tot,m[1005];
int main()
{
cin>>n>>w;
for(int i=1;i<=n;i++)
cin>>u[i]>>v[i]>>m[i],_m[i]=m[i];
int i,j;
for(i=1;i<=n;i++)
{
for(j=0;(1<<j)<=m[i];j++)
m[i]-=(1<<j),_u[++tot]=u[i]*(1<<j),_v[tot]=v[i]*(1<<j);
if(m[i])
_u[++tot]=u[i]*m[i],_v[tot]=v[i]*m[i];
}
for(int i=1;i<=tot;i++)
for(int j=w;j>=_v[i];j--)
f[j]=max(f[j-_v[i]]+_u[i],f[j]);
cout<<f[w];
return 0;
}