HDU3466 Proud Merchants

一、题目内容

【题目描述】

现在n个物品，每组物品有三个属性，pi，买这种物品你需要花费的钱，vi,该物品的价值。qi,如果你想要买这种物品你所拥有的钱必须大于qi。
问你能用你所有的钱最多能获得多大价值。
(每个物品只能买一次）

【输入格式】

有多组测试数据。
对于每组测试数据开始时有两个书N,M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000);分别表示物品的编号和你所拥有的钱数。
然后是N行，每行包含三个数字Pi，Qi和Vi（1≤Pi≤Qi≤100,1≤Vi≤1000），它们的含义在描述中。
输入终止于文件结束标记。

【输出格式】

对于每个测试用例，输出一个整数，表示你可以得到的物品的价值总和的最大值。

【输入样例】

2 10

10 15 10

5 10 5

3 10

5 10 5

3 5 6

2 7 3

【输出样例】

2

4

6

【测试网站】

HDU3466

二、题目分析

因为每个物品都有一个限制q，而01背包dp是从前i个物品转移到前i+1个物品，所以必须保证转移时无后效性，即前面i个物品选择的结果不会影响到后面的选择.
在这里体现在前i个物品中会影响的范围为q-p;如果第i+1个物品的q-p > 前i个物品的q-p,则可以保证如果选择第i个物品，那么前面i+1个物品的q的限制条件都能满足。 即 qi+1 在的位置>qi

三、代码示例

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 510;
const int INF = 0x3f3f3f3f;

int n,m;
int dp[5005];
struct Node
{
  int p,q,v;
}a[maxn];

bool cmp (Node a, Node b)
{
  return a.q - a.p < b.q - b.p;
}

int main()
{
  while(~scanf("%d%d",&n,&m))
  {
    for(int i = 0; i < n; i++) scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
    sort(a,a+n,cmp);//排序
    memset(dp,0,sizeof(dp));//初始化dp数组
    for(int i = 0; i < n; i++)
       for(int j = m; j >= a[i].q; j--)
            dp[j] = max(dp[j],dp[j-a[i].p] + a[i].v);//无后效性dp
    printf("%d\n",dp[m]);
  }
  return 0;
}