这题数据范围很松,暴力搞也是可以的。这里提供两个方法:
暴力版:
复杂度$~O(NVS)~$
#include<iostream>
using namespace std;
const int N = 6005;
int n,t;
int f[N];
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int j=t;j;j--)
for(int k=1;k<=s && k*v<=j;k++)
f[j]=max(f[j],f[j-k*v]+k*w);
}
cout<<f[t];
return 0;
}
二进制优化版:
复杂度:$O(NVlogS)$
思路:
因为物品数量的约束为$s$,我们对$s$先进行分组。
比如$s=12$时,我们可以按照$1,2,4$的个数进行拆分,发现还剩$5$个,我们只需将最后的$5$个看成一个整体(作为$01$背包中的物品看待即可)
可以证明这样分组覆盖了所有情况:这里就拿上面的例子说明成立(非证明):
可以知道$1,2,4$的拆分方案覆盖了$1-7$的所有情况,而对于剩下的$5$,只需在$1-7$的基础上加上$5$即可覆盖$6-12$的情况,综上覆盖了$1-12$的所有情况。
#include<iostream>
using namespace std;
const int N = 2021;
int n,t;
int f[N];
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int k=1;k<=s;k<<=1){
s-=k;
for(int j=t;j;j--)
if(j>=k*v) f[j]=max(f[j],f[j-k*v]+k*w);
}
if(s)
for(int j=t;j;j--)
if(j>=s*v) f[j]=max(f[j],f[j-s*v]+s*w);
}
cout<<f[t];
return 0;
}