1 //Accepted    868 KB    188 ms 2 //多重背包 3 #include <cstdio> 4 #include <cstring> 5 #include <iostream> 6 #include <queue> 7 #include <cmath> 8 #include <algorithm> 9 using namespace std;10 /**11   * This is a documentation comment block12   * 如果有一天你坚持不下去了，就想想你为什么走到这儿！13   * @authr songt14   */15 const int imax_v = 40005;16 const int imax_n = 405;17 int dp[imax_v];18 int n;19 struct node20 {21     int weight,c,a;22 }f[imax_n];23 //按a排序，考虑我们在dp时采用的是倒推，所以我们需要先计算出a较小的时候的情况24 int cmp(node x,node y)25 {26     return x.a<y.a;27 }28 int max(int a,int b)29 {30     return a>b?a:b;31 }32 void zeroOnePack(int weight,int value,int v)33 {34     for (int j=v;j>=weight;j--)35     {36         dp[j]=max(dp[j],dp[j-weight]+value);37     }38 }39 void completePack(int weight,int value,int v)40 {41     for (int j=weight;j<=v;j++)42     {43         dp[j]=max(dp[j],dp[j-weight]+value);44     }45 }46 void multiplePack(int weight,int value,int amount,int v)47 {48     int k=1;49     if (amount*weight>=v)50     {51         completePack(weight,value,v);52         return ;53     }54     while (k<amount)55     {56         zeroOnePack(k*weight,k*value,v);57         amount-=k;58         k<<=1;59     }60     zeroOnePack(amount*weight,amount*value,v);61 }62 void Dp()63 {64     memset(dp,0,sizeof(dp));65     for (int i=1;i<=n;i++)66     {67         multiplePack(f[i].weight,f[i].weight,f[i].c,f[i].a);68     }69     int ans=0;70     for (int i=1;i<=40000;i++)71     ans=max(ans,dp[i]);72     printf("%d\n",ans);73 }74 int main()75 {76     while (scanf("%d",&n)!=EOF)77     {78         for (int i=1;i<=n;i++)79         scanf("%d%d%d",&f[i].weight,&f[i].a,&f[i].c);80         sort(f+1,f+n+1,cmp);81         Dp();82     }83     return 0;84 }