hdu 3466 Proud Merchants 贪心+01背包

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3466

题意：N个物体，M的钱，每个有pi, qi, vi。表示当钱的数量 >= qi的时候才可以买这个物品，要花掉pi的钱，价值为vi。求买完后能获得的最大价值。

思路：

考虑有两个物品A和B，总共的钱是M。

假设M > pa且M > pb。

假设先买A，那么买B的时候，需要的钱至少为qb，即如果想继续买B，(M - pa) > qb。

同理假设先买B，那么买A的时候，需满足(M - pb) > qa。

所以这两者造成的结果不同，那么这是一个需要先进行贪心的背包。

考虑转移方程 dp[j] = max(dp[j], dp[j-node[i].p] + node[i].v);

可以发现，每次更新的值是在[node[i].q - node[i].p, M]这个区间中的。

所以把q-p按从小到大排序，可以保证更新的时候从小到大。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int N, M;
 4 struct Node
 5 {
 6     int p, q, v;
 7 }node[510];
 8 int dp[5010];
 9 bool cmp(Node a, Node b)
10 {
11     return (a.q - a.p) < (b.q - b.p);
12 }
13 int main() 
14 {
15   //  freopen("in.txt", "r", stdin);
16     while(~scanf("%d%d", &N, &M))
17     {
18         for(int i = 1; i <= N; i++)
19         {
20             scanf("%d%d%d", &node[i].p, &node[i].q, &node[i].v);
21         }
22         memset(dp, 0, sizeof(dp));
23         sort(node+1, node+1+N, cmp);
24         for(int i = 1; i <= N; i++)
25         {
26             for(int j = M; j >= node[i].q; j--)
27             {
28                 dp[j] = max(dp[j], dp[j-node[i].p] + node[i].v);
29             }
30         }
31         printf("%d
", dp[M]);
32     }
33     return 0;
34 }