题目描述
背包系列dp问题
1.（01背包）
01背包：只能用一次求最大价值。
dp
1.状态表示f[i][j]
i表示前i个物品 j表示体积 属性：前i个物品的在j的体积下的最大价值
2.状态转移
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
优化：f[j]=max(f[j],f[j-v[i]]+w[i])
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
注意：优化的时候第二重循环应该 反着循环
因为f[i-1][j-v[i]]+w[i]——>f[j-v[i]]+w[i] 反着才等价
不然就成了完全背包
2.（完全背包）
完全背包：能用无限次求最大价值。
dp
1.状态表示f[i][j]
i表示前i个物品 j表示体积 属性：前i个物品的在j的体积下的最大价值
2.状态转移
f[i][j]=max(f[i-1][j],f[i-1][j-mv[i]]+w[i]*m) m 表示这件物品在不超过体积的情况下用的个数
上式推导可得下面
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])
优化：f[j]=max(f[j],f[j-v[i]]+w[i])
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])
注意：优化的时候第二重循环应该 正着循环
因为f[i-1][j-v[i]]+w[i]——>f[j-v[i]]+w[i] 正着才等价
不然就成了01背包
3.（多重背包1）
多重背包1：能用n次求最大价值。
主要思想：通过在输入过程中将n拆分成 n个1 这样就相当于01背包问题如上
1.状态表示f[i][j]
i表示前i个物品 j表示体积 属性：前i个物品的在j的体积下的最大价值
2.状态转移
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
优化：同上
4.（多重背包2）
多重背包1：能用n次求最大价值,数据较大暴力会tle。
主要思想：通过二进制优化 这样就相当于01背包问题如上
sum表示现在已经拆分的总和
二进制优化：将n拆分成 1 2 4 8 16 32 .... 2^m-1 2^m n-sum;
你会发现这组数可以构成1-n 任意一个数；
比如我需要 3只需要1+2就可以
1.状态表示f[i][j]
i表示前i个物品 j表示体积 属性：前i个物品的在j的体积下的最大价值
2.状态转移
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
优化：同上
5.（分组背包）
分组背包：有多组不同类型的物品，每一组物品只能选择其中的一个，求最大价值
思想：类似于01背包但需要加一层循环来判断该组物品的最优解
dp
1.状态表示f[i][j]
i表示前i组物品 j表示体积 属性：前i组物品的在j的体积下的最大价值
2.状态转移
f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k])
总结：
所有的背包问题都可以用01背包转化优化得到。
背包的所有ac码如下
01背包
#include<iostream>
using namespace std;
int const maxn=1e3+10;
int f[maxn][maxn];
int w[maxn],v[maxn];
//f[i][j]=f[i-1][j],f[i-1][j-v[i]]+w[i];
int main()
{
int n,m; 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][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
完全背包
#include<iostream>
using namespace std;
int const maxn=1e3+10;
int f[maxn][maxn];
int v[maxn],w[maxn];
int main()
{
int n,m; 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][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m]<<endl;
}
多重背包1
#include<iostream>
using namespace std;
int const maxn=11000;
int v[maxn],w[maxn],idx;
int f[maxn];
int main()
{
int n,m; cin>>n>>m;
for(int i=1;i<=n;i++)
{
int vv,ww,t; cin>>vv>>ww>>t;
while(t--)
{
idx++;
v[idx]=vv; w[idx]=ww;
}
}
for(int i=1;i<=idx;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
多重背包2
#include<iostream>
using namespace std;
int const maxn=2e6+10;
int f[maxn],idx;
int v[maxn],w[maxn];
int main()
{
int n,m; cin>>n>>m;
while(n--)
{
int tv,tw,t; cin>>tv>>tw>>t;
for(int i=1;i<=t;i*=2)
{
idx++;
v[idx]=tv*i; w[idx]=tw*i;
t-=i;
}
if(t) v[++idx]=t*tv,w[idx]=t*tw;
}
for(int i=1;i<=idx;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m]<<endl;
}
分组背包
#include<iostream>
using namespace std;
int const maxn=1e2+10;
int f[maxn][maxn];
int v[maxn][maxn];
int w[maxn][maxn];
int n[maxn];
int main()
{
int kind,big; cin>>kind>>big;
for(int i=1;i<=kind;i++)
{
cin>>n[i];
for(int j=1;j<=n[i];j++)
{
cin>>v[i][j]>>w[i][j];
}
}
for(int i=1;i<=kind;i++)
{
for(int j=0;j<=big;j++)
{
f[i][j]=f[i-1][j];
for(int k=1;k<=n[i];k++)
{
if(j>=v[i][k]) f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[kind][big]<<endl;
}
