题目
思路
这是一道多重背包的典型模板题,对着代码抄即可。这题因为数据大,AC要用到优化,但由于本人是个辣鸡,所以只能打个最普通的代码了。
代码
#include<cstdio> #include<iostream> using namespace std; int n,n1,f[40001],v[101],w[101],m[101]; int main() { scanf("%d%d",&n,&n1); for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&m[i]); for(int i=1;i<=n;i++) for(int j=n1;j>=0;j--) for(int k=0;k<=m[i];k++) if(w[i]*k>j) break; else f[j]=max(f[j],f[j-k*w[i]]+k*v[i]); printf("%d",f[n1]); return 0; }