Proud Merchants

题目链接：

https://vjudge.net/contest/348156#problem/I

题面：

翻译：

最近，伊萨去了一个古老的国家。在这么长的时间里，它是世界上最富有和最强大的王国。因此，即使他们的国家不再那么富有，这个国家的人民仍然非常自豪。
商人是最典型的，他们每个人只卖一件商品，价格是Pi，但如果你的钱少于Qi，他们会拒绝与你做交易，而伊萨评估每件商品的价值为Vi。
如果他有M单位的钱，ISEA的最大值是多少？

输入：
输入中有几个测试用例。
每个测试用例以两个整数N，M（1≤N≤500，1≤M≤5000）开头，表示项目编号和初始金额。
接下来是N行，每行包含三个数字Pi，Qi和Vi（1≤Pi≤Qi≤100，1≤Vi≤1000），其含义在描述中。
输入以文件尾标记结束。

输出：
对于每个测试用例，输出一个整数，指示最大值ISEA可以得到。

思路：

这道题目比起普通的01背包又灵活些一些，题目要求是一定你的钱大于q才让你花费p的钱去卖给你价值为v的物品，而要使得最后的价值最大。这道题目就是加了一个限制的金钱数，但是还是和价格有关，当限制一样价格不同时顺序就影响结果。一种组合的排序策略–限制又小价格又贵的先选，也就是q-p小的先选。为什么这样呢？A：p1,q1 B: p2,q2，先选A，则至少需要p1+q2的容量，而先选B则至少需要p2+q1，如果p1+q2>p2+q1，那么要选两个的话的就要先选A再选B，公式可换成q1-p1 > q2-p2，就按这样的方法排序最后的顺序就是最优的顺序。
该题要确保P[i]-Q[i]小的先被”挑选“，差值越小使用它的价值越大(做出的牺牲越小).

参考代码：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int n,m;
int dp[50005];
struct node
{
    int p,q,v;
}a[50005];
bool cmp(node a,node b)
{
    return a.q-a.p < b.q-b.p;//通过结构体排序来首先q-p的数值从小到大排序
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
            scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
        sort(a+1,a+n+1,cmp);
        memset(dp,0,sizeof (dp));
        for(int i=1;i<=n;i++)
        {
            for(int j=m;j>=a[i].q;j--)//这里限制j的不在是a[i].p而是a[i].q因为题目是说要大于a[i].q才可以去购买
            {
                    dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);
                
            }
        }
        printf("%d\n",dp[m]);
    }
    return 0;
}