AcWing 5. 多重背包问题 II
原题链接
中等
作者:
逸误
,
2023-07-16 05:50:36
,
所有人可见
,
阅读 94
//二进制优化的思路:将同一个物品分为1,2,4,8,...个
//于是可以组合出任意个这个物品,将多重背包问题简化为了01背包问题!
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12010,M = 2010;//二进制优化的多重背包,物品个数最多是N*logS。
int n,m;
int v[N],w[N];
int f[M];//用一维优化“01背包”问题
int main()
{
cin>>n>>m;
int cnt=0;//记录存到哪了,类似idx
for(int i=1;i<=n;i++)//一次循环是一种物品
{
int a,b,s;//分别是v,w,s
scanf("%d%d%d",&a,&b,&s);
int k=1;//k表示本组分出了此物品中的几个
while(k<=s)//这组分为k个
{
v[++cnt]=a*k;//k个此物品的体积
w[cnt]=b*k;//k个此物品的价值
s-=k;//还剩下多少要分
k*=2;//下一组翻倍
}
if(s>0)//剩下来的分一组,s个
{
v[++cnt]=a*s;
w[cnt]=b*s;
}
}
n=cnt;//二进制优化之后,更新n
//下面处理01背包问题即可
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)//一维数组优化的01背包问题同一列中反着来
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m]<<endl;
return 0;
}
二进制优化的根本想法就是把同种的多个物品给拆分成多种的单个物品,于是可以简化为01背包问题!