KY139 毕业bg
背包问题，不过时间要从后往前考虑
ti
#include<bits/stdc++.h>
using namespace std;
struct bg{
int h, t1, t2;
}m[35];
bool cmp(bg a, bg b){
return a.t2 < b.t2;
}
int k;
int nb;
int dp[1010];
int main()
{
while(cin>>nb){
if(nb == -1) break;
memset(dp, 0, sizeof(dp));
memset(m, 0, sizeof m);
int maxt = -1;
for(int i = 0; i < nb; i ++ ){
cin>>m[i].h>>m[i].t1>>m[i].t2;
maxt = max(maxt, m[i].t2);
}
//cout<<maxt<<endl;
sort(m, m + nb, cmp);
int res = -1;
for(int i = 0; i < nb; i ++ ){ //活动
for(int j = m[i].t2; j >= 0; j -- ){ //时间
if(j - m[i].t1 >= 0){ //这个活动能去
dp[j] = max(dp[j], dp[j - m[i].t1] + m[i].h);
res = max(res, dp[j]);
}
}
}
cout<<res<<endl;
}
return 0;
}