1.数组大小:对一种物品的数量依托二进制进行划分,得到的结果数量大概有log(s)个,设题目物品种类有n种,则数组大小至少要大于n*log(s)
#include <iostream>
using namespace std;
const int N=25000;//由n*log(s)估计得
int n,m,cnt=0;
int v[N],w[N],f[N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int a,b,s;
cin>>a>>b>>s;
//对s的值进行划分,划分结果形如1 2 4 8
int k=1;
while(k<=s)
{
cnt++;
v[cnt]=k*a;
w[cnt]=k*b;
s-=k;//控制所有k值加起来不会超过s
k*=2;
}
if(s>0)
{
cnt++;
v[cnt]=s*a;
w[cnt]=s*b;
}
}
n=cnt;//容易遗漏的一步
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}//按照01背包的选择方式?
cout<<f[m];
return 0;
}