HDU 3466 Proud Merchants（0-1背包）

 1 #include<iostream> 
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 
 6 const int maxn = 5000+5;
 7 
 8 int n, m;
 9 int dp[maxn];
10 
11 struct node
12 {
13     int p, q, v;
14 }a[maxn];
15 
16 bool cmp(node a, node b)
17 {
18     return a.q-a.p < b.q-b.p;
19 }
20 
21 int main()
22 {
23     //freopen("D:\\txt.txt", "r", stdin);
24     while (cin >> n >> m && n && m)
25     {
26         memset(dp, 0, sizeof(dp));
27         for (int i = 1; i <= n; i++)
28             cin >> a[i].p >> a[i].q >> a[i].v;
29         sort(a + 1, a + 1 + n, cmp);
30         for (int i = 1; i <= n; i++)
31         {
32             for (int j = m; j >= a[i].q; j--)
33                 dp[j] = max(dp[j], dp[j - a[i].p] + a[i].v);
34         }
35         cout << dp[m] << endl;
36     }
37     return 0;
38 }