01背包问题动态规划应用

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 struct BG 6 { 7     int h,t,l; 8     friend bool operator<(BG a,BG b)     9     {10         return a.l<b.l;11     }12 };13 BG *bg;14 int main()15 {16     int n,m;17     int value[3500];18     while(cin>>n&&n>=0)19     {20         m=0;21         if(n==0)22         {23             cout<<0<<endl;24             continue;25         }26         bg=new BG[n];27         memset(value,0,sizeof(value));28         for(int i=0;i<n;i++)29         {30             cin>>bg[i].h>>bg[i].t>>bg[i].l;31             m=(bg[i].l>m)?bg[i].l:m;32         }33         sort(bg,bg+n);34         for(int i=0;i<n;i++)35         {36             for(int j=bg[i].l;j>=bg[i].t;j--)37             {38                 value[j]=max(value[j],value[j-bg[i].t]+bg[i].h);39             }40         }41         int ans=0;42         for(int i=0;i<=m;i++)43         {44             if(value[i]>ans)ans=value[i];45         }46         cout<<ans<<endl;47     }48     return 0;49 }