核心思想: 二进制优化
将s拆成若干份可以表示s以内所有数字 (例如7 –> 1 2 4 可以表示出7以内所有数字)
即转换成二进制拆出 然后将拆出的部分按照大小扩大 就成了01背包问题了
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 2010;
int n,m;
int f[N];
struct Good{
int v,w;
};
int main()
{
vector<Good> goods;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int v,w,s;
cin>>v>>w>>s;
for(int k=1;k<=s;k*=2) //二进制拆
{
s -= k;
goods.push_back({v*k,w*k}); //存入时 按照倍数扩大v和w
}
if(s>0) goods.push_back({s*v,s*w}); //扩大s倍存入
}
for(auto good : goods) //01背包
{
for(int j=m;j>= good.v ;j--)
{
f[j] = max(f[j] , f[j - good.v] + good.w);
}
}
cout<<f[m];
}
不用结构体存 也可以用数组v[N],w[N]存