思路:按高度的限制大小排序,再多重背包
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cmath> #define CL(a,b) memset(a,b,sizeof(a)) #define MAX(a,b) (a>b?a:b) #define MIN(a,b) (a<b?a:b) #define INF 0x7ffffff using namespace std; const int M(40010); const int N(410); int f[M]; struct data{ int h,c,a; }val[N]; bool cmp(data x,data y) { return x.a<y.a; } int main() { int n,i,j,k; while(scanf("%d",&n)!=EOF) { int maxm=0,sum=0; for(i=0;i<n;i++) { scanf("%d%d%d",&val[i].h,&val[i].a,&val[i].c); maxm=MAX(maxm,val[i].a); } sort(val,val+n,cmp); CL(f,0); for(i=0;i<n;i++) { j=1; while(j<val[i].c) { for(k=maxm;k>=j*val[i].h;k--) if(f[k-j*val[i].h]+j*val[i].h<=val[i].a) f[k]=MAX(f[k],f[k-j*val[i].h]+j*val[i].h); val[i].c-=j; j<<=1; } j=val[i].c; for(k=maxm;k>=j*val[i].h;k--) if(f[k-j*val[i].h]+j*val[i].h<=val[i].a) f[k]=MAX(f[k],f[k-j*val[i].h]+j*val[i].h); } sum=0; for(k=0;k<=maxm;k++) sum=MAX(sum,f[k]); printf("%d\n",sum); } }