混合背包问题
题目 混合背包问题
思路分析
学过了01背包 完全背包 多重背包
不难发现他们都是极其相似的
首先01背包用的是从大到小枚举体积 因为它要用的是上一层的数据
完全背包用的是第i层的数据 由此使用从小到大枚举体积
而多重背包有两种理解方式 一是把它当成01背包看 先把所有物品用二进制优化 拆分成多个01背包里的物品 写法就和01完全一样了 从大到小枚举体积 二是当成完全背包来看 把所有的mod余相等的当做同一类物品 这些物品之间相互独立 只需要使用滑动窗口取出每一类中的最大值即可
这里多重背包还是选择使用二进制好些 更容易理解
使用二进制优化的多重背包 与01背包是完全一样的 那么如何合并起来呢
发现01背包不过就是某类物品只能选一次的多重背包吧（s[i]=1)
那么问题就基本解决了
三个问题变成了两个问题
碰到完全背包（无限选的）用一种写法
碰到01背包把它变成s[i]=1的多重背包 再把多重背包进行二进制拆分 合起来用一种写法
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct Thing{
int kind;
int v,w;
};
vector<Thing> things;
int dp[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
if(s==-1)//如果该物品是01背包的 存-1标记
things.push_back({-1,v,w});
else if(s==0)
things.push_back({0,v,w});
else{//如果是多重背包的 把它拆成多个01背包
for(int k=1;k<=s;k*=2){
things.push_back({-1,v*k,w*k});
s-=k;
}
if(s>0)
things.push_back({-1,v*s,w*s});
}
}
for(auto thing:things){
if(thing.kind==-1)
for(int j=m;j>=thing.v;j--)//01背包 从大到小
dp[j]=max(dp[j],dp[j-thing.v]+thing.w);
else
for(int j=thing.v;j<=m;j++)//完全背包 从小到大
dp[j]=max(dp[j],dp[j-thing.v]+thing.w);
}
cout<<dp[m];
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int v[N],w[N],s[N];
int dp[N];
int n,m;
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++){
if(s[i]==0)//完全背包 从小到大
for(int j=v[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
else//01和多重合在一起
{
if(s[i]==-1)
s[i]=1;//01背包就是该物品只能选一次的情况 直接让s[i]>0 且等于1即可
for(int k=1;k<=s[i];k*=2){
for(int j=m;j>=k*v[i];j--){
dp[j]=max(dp[j],dp[j-k*v[i]]+k*w[i]);
}
s[i]-=k;
}
if(s[i]){
for(int j=m;j>=s[i]*v[i];j--){
dp[j]=max(dp[j],dp[j-s[i]*v[i]]+s[i]*w[i]);
}
}
}
}
cout<<dp[m];
return 0;
}
//思路虽然更巧妙 直接一气呵成 但是效率反而更低了些 上面138ms 这个166ms
//这个写法用于练手，深入理解用 真正写这类题的话还是用上面的stl 条理清晰
💬 评论