学步园

二进制拆包！多重背包！！出显小错误wa了好几次！！！！！不做什么解释了！！！！

 #include<iostream>
using namespace std;
#include<algorithm>
long long dp[40005];
struct node
{
 int h;
 int b;
 int c;
}a[500];
bool cmp(node x,node y)
{
 return x.b<y.b;
}
int main()
{
 int n;
 while(cin>>n)
 {
  for(int i=1;i<=n;i++)
  cin>>a[i].h>>a[i].b>>a[i].c;
  sort(a+1,a+1+n,cmp);
  memset(dp,0,sizeof(dp));
  for(int i=1;i<=n;i++)
  {
   int k=1;
   int t=a[i].c;
   while(k<=t)//二进制拆包了！！！
   {
    int temp=k*a[i].h;
    for(int j=a[i].b;j>=temp;j--)
    dp[j]=max(dp[j-temp]+temp,dp[j]);
    t-=k;
    k<<=1;//乘二
   }
   int temp=a[i].h*t;//将剩余的在刷一遍
   for(int j=a[i].b;j>=temp;j--)
   dp[j]=max(dp[j-temp]+temp,dp[j]);
  }
  int max=0;
  for(int i=1;i<=a[n].b;i++)//我感觉这个有点不好费时间，但也没优化
  if(dp[i]>max)
  max=dp[i];
  cout<<max<<endl;
 }
 return 0;
}