数据范围
0<N≤1000
0<V≤2000
0<vi,wi,si≤2000
样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
NVm会超时,用二进制优化为01背包(1,2,4,8…)可以组合出任意的一个要选取物品的数量,只剩下选不选的问题
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=11500;//2^10=1024,2^11=2048,1000种苹果划分最多有11000
int v[N],w[N];
int a,b,c,n,m,cnt=1;
int f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)//把一种果子分成二进制的若干堆
{
cin>>a>>b>>c;
int temp=1;
while(c>=temp)
{
v[cnt]=temp*a;
w[cnt]=temp*b;
cnt++;
c-=temp;
temp*=2;
}
if(c>0) v[cnt]=c*a, w[cnt]=c*b,cnt++;
}
//for(int i=1;i<=cnt;i++) cout<<v[i]<<" "<<w[i]<<endl;
for(int i=1;i<=cnt;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
cout<<f[m];
}