背包dp复习笔记
对于所有背包dp问题
dp[i][j] 表示前 i 个物品在背包容量为 j 时的最大价值
01背包
二维写法模板
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
(其中 w[i] v[i] 分别表示第 i 个物品的体积和价值）
对于每个 dp[i][j] 都只与 dp[i-1][j] 和 dp[i-1][j-w[i]] (上方) 有关
所有我们可以开一个一维数组实现空间上的优化
dp[j] 表示在背包容量为 j 时的最大价值
为防止前面 dp 的值被覆盖影响后面的 dp 所有遍历背包容量时应逆序
一维写法模板
for(int i=1;i<=n;i++){
for(int j=m;j>=w[i];j--){
dp[j]=max([j],dp[j-w[i]]+v[i]);
}
}
例题 <1478> 采药 <3355> 美丽手镯
完全背包
二维写法模板
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
dp[i][j]=dp[i-1][j];
if(j>=w[i]) dp[i][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
}
}
同理每个 dp[i][j] 都只与 dp[i-1][j] 和 dp[i][j-w[i]] (前方与上方) 有关
所有遍历背包容量时应为正序
一维写法模板
for(int i=1;i<=n;i++){
for(int j=w[i];j<=m;j++){
dp[j]=max([j],dp[j-w[i]]+v[i]);
}
}
例题 <21596>【例86.3】 完全背包问题
多重背包
多重背包与01背包的唯一不同点就是个数上的限制
一维写法模板
for(int i=1;i<=n;i++){
for(int j=m;j>=0;j--){
for(int k=0;k<=p[i];k++){
if(k*w[i]<=j) dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
}
}
}
(其中 p[i] 表示第 i 个物品的个数）
例题 <3668> 混合背包
分组背包
在01背包的基础上枚举每组选择的物品即可
for(int i=1;i<=t;i++){
for(int j=m;j>=0;j--){
for(int k=index;k<=index+cnt[i]-1;k++){
if(obj[k].w<=j) dp[j]=max(dp[j],dp[j-obj[k].w]+obj[k].v);
}
}
index+=cnt[i];
}
(其中 t 表示最大组号，cnt[i] 表示第 i 组的物品个数，物品按组号升序排序）
例题 <3675> 分组背包
背包变形
这里我们看两道例题
<15072> 寿司选择 <7158> 抢劫银行
寿司选择
因为本题求的是最小花费 所以 dp[j] 为能否选出价格和为j的寿司组合
如果可以的话 dp[j]=j 否则 dp[j]=0x3f
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,m,a[205],dp[N],sum,ans=0x3f3f3f3f;
int main(){
memset(dp,0x3f3f3f,sizeof(dp));
dp[0]=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
for(int i=1;i<=n;i++){
for(int j=sum;j>=a[i];j--){
dp[j]=min(dp[j],dp[j-a[i]]+a[i]);
}
}
for(int i=m;i<=sum;i++){
ans=min(ans,dp[i]);
}
cout<<ans;
}
抢劫银行
每次被抓的概率为 p[i] 那不被抓的概率为 1-p[i]
所以行动 k 次不被抓的概率为 \prod_{i=1}^k1-p[i]
与上体类似 dp[j] 为能否得到j元的抢劫方案
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e2+5;
int main(){
int t;
cin>>t;
while(t--){
double x,p[N],dp[N*N];
int n,m[N];
memset(dp,0,sizeof(dp));
int sum=0,ans=0;
cin>>x>>n;
dp[0]=1.0;
for(int i=1;i<=n;i++){
cin>>m[i]>>p[i];
sum+=m[i];
}
for(int i=1;i<=n;i++){
for(int j=sum;j>=m[i];j--){
dp[j]=max(dp[j],dp[j-m[i]]*(1-p[i]));
}
}
for(int i=sum;i>=0;i--){
if(1-dp[i]==x){
ans=i;
break;
}
}
cout<<ans<<endl;
}
}
因为浮点数累乘会出现精度问题 所以最后我们应判断
if(1-dp[i]+1e-8<x)
而不是简单判等
吧