多重背包问题II(二进制优化)
思路
这个比原问题难就难在数据范围更大,如果不采用二进制优化是过不了的,我个人理解这个方法也就是对原问题的一个等价转化,转化成了一个01背包问题!
见: https://www.acwing.com/solution/content/20115/
代码
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=2e3+10;
int n,v,f[N];
typedef pair<int,int> PII;
vector<PII> things;
int main()
{
cin>>n>>v;
for(int i=1;i<=n;i++)
{
int v,w,s;
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2)
{
s-=k;
things.push_back({v*k,w*k});
}
if(s>0)
things.push_back({v*s,w*s});
}
for(auto x:things)
{
for(int j=v;j>=x.first;j--)
f[j]=max(f[j],f[j-x.first]+x.second);
}
cout<<f[v]<<endl;
return 0;
}