Proud Merchants HDU

最近，我去了一个古老的国家。在很长一段时间里，它是世界上最富有、最强大的王国。结果，这个国家的人民仍然非常自豪，即使他们的国家不再那么富有。商人是最典型的，他们每个人只卖一件商品，价格是Pi，但是如果你的钱少于Qi，他们就会拒绝和你交易，而我评估每件商品的价值Vi。如果他有M单位的钱，iSea能得到的最大值是多少?

输入

在输入中有几个测试用例。每个测试用例以两个整数N M(1≤N≤500,1≤M≤5000)开始，表示项目编号和初始资金。接着N行，每一行包含3个数字Pi, Qi和Vi(1≤Pi≤Qi≤100,1≤Vi≤1000)，它们的含义在描述中。输入在文件标记结束时终止。

输出

对于每个测试用例，输出一个整数，表示iSea可以获得的最大值。

Sample Input

2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3

Sample Output

5
11

题解：

这道题和01背包有什么不同呢？

给你两个物品：（现在你手里有钱17）

一、物品价值P1=5  ，物品Q1=12

二、物品价值P2=10  ，物品Q2=10

如果你第一次买第一个物品，那么你还可以买第二个物品

但是如果你第一次买第二个物品，你就买不了第一个物品了。

所以这就涉及到了物品买的顺序的问题了

正常01背包dp方程dp[j]=max(dp[j],dp[j-Pi])

那么也就是说dp[j]中存放的最优解是从dp[j]或者dp[j-Pi]中获得的（因为我得01背包用的滚动数组压缩内存，所以dp[j]也可以是从上一级dp循环中的最优解）

重要的是dp[j-Pi]

dp[j]代表什么意思？就是你有空间为j的时候你能获得的最大价值

那么因为dp[j]的一个状态是从dp[j-Pi]转移过来的，所以也就是说j-Pi这一部分空间已经被使用完了

那么我们要保证这个物品可以买，就只有当m-(j-Pi)>=Qi条件满足的时候才有资格买这个物品 （m在这代表你拥有的钱的总数，初始资金）

可能大家有点疑惑，在01背包的第二层for循环中就是枚举钱为j时候能获取的最大价值，那么为什么还要用到m-j这一部分钱来判断呢？

因为最后我们要的结果就是在初始资金为m的时候能获取最大价值，所以中间的dp状态如果能买这个物品那就买（大家还是自己想想吧）

又因为j>=Pi且m-(j-Pi)>=Qi

得到：Pi<=j<=m-(Qi-Pi)

又因为我们要保证无后效性，即前面的在更新时对后面的决策无影响。那么后面的d[j-p[i]]这个状态肯定在前面已经更新到了。所以就是说前面的更新的范围应该比后面大。

所以就是P1 - Q1 > P2-Q2;即按照P-Q从大到小排序,或者Q - P按照从小到大排序才能保证后面的能更新到不丢失状态。

代码：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int max(int x,int y)
{
    if(x>y) return x;
    else return y;
}
struct goods
{
    int money,lesses,value;
}m[1005];
bool mmp(goods x,goods y)
{
    return (x.lesses-x.money)<(y.lesses-y.money);
}
int v[5005];
int main()
{
    int a,s,d,f,g;
    while(~scanf("%d%d",&a,&s))
    {
        memset(v,0,sizeof(v));
        for(d=1;d<=a;++d)
            scanf("%d%d%d",&m[d].money,&m[d].lesses,&m[d].value);
        sort(m+1,m+a+1,mmp);
        for(d=1;d<=a;++d)
        {
            for(f=s;f>=m[d].lesses;--f)  //注意这里不是money，因为有lesses的限制
            {
                v[f]=max(v[f],v[f-m[d].money]+m[d].value);
            }
        }
        printf("%d
",v[s]);
    }
    return 0;
}