此题我纠结了一下午，最终。。。。。。还是没想出来。然后看了神牛的题解 说是 按 q-p 排序。。。 于是我就去想为什么按此排序。。
在雨中漫步了一会，今晚的济南的正好下雨，但还是习惯性走出实验室，思考了十几分钟之后，终于想通了。。。。 于是就在这写题解。。。
我感觉这是一个好题。。。。。。。。
Proud Merchants
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/65536 K (Java/Others)
Total Submission(s): 1210 Accepted Submission(s): 508
more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.
2 10 10 15 10 5 10 5 3 10 5 10 5 3 5 6 2 7 3
5 11
题意是： 给你一些钱 m ，然后在这个国家买东西， 共有 n 件物品，每件物品有 价格 P 价值 V 还有一个很特别的属性 Q, Q 指 你如过想买这件物品 你的手中至少有这钱Q 。 虽然你只要花费 钱P ，但你的手中至少有钱Q，如果不足Q ，不能买。问给你钱M ，列出N件物品，最多能获得多少价值的东西。。。。
第一眼看是个DP。。。。 但是想了许久都想不出 状态转移方程。。。
废话不多说。 给出解题思路。。。。。
解： 按 Q-P 的大小 ，从小到大排序，然后按照0-1 背包的思想
dp[c]=max(dp[c],dp[c-p[i]])+v[i]; 最终 dp[m]就是结果。
思路很简单，但是很难想。
在这我给出为什么要按Q-P排序的证明
一。 首先，不想为什么 ，要按照Q-P 排序。我们先想这么一个问题，（原因一会就知道了）。
给你n 个这种商品，你最少需要多少钱能够买下来。。(通过这个问题，可以找出一个性质)
再把这个商品转化 一下。。
还是有三个属性 P 价格 、V 价值 、 M 为Q-P。
Sum = P1 +P2 +P3 +........+Pn+max(Mi-(P(i+1)+P(i+2)+...........Pn))；
要使得Sum 最小 就应该按照 M从大到小排序 (这里就是从大到小，没错)，然后0-1背包求解。
证明：
如果看不懂公式 是什么 意思。。。没关系
那你就看 这样一个题的题解。。。这里有相同的公式（很简单的）
http://blog.csdn.net/oceanlight/article/details/7862104
这是我昨天写的一个题的题解，真没想到今天会用到的。。。
如果你看完了，你就应该懂了 。 要得到最小的sum ，就应该按照 M 从大到小排序了吧
也就是说我们应该先买M最大的物体，然后买M第二大的 。。。。。 最后买最小的。。。这个性质是这个问题的关键。
二。给一定的钱 ，我们的购买方式是 应该先买M最大的物体(M=Q-P)，然后依次买第二大、第三大、、、、、
我们已经知道这个购买方式，怎么实现就要用到DP 中的0-1背包的思想了。
dp[c]=max(dp[c],dp[c-p[i]])+v[i]; c 为第c 个物品。这是用一维数组实现01背包。。
dp[c-p[i]] 是指 我们在容量为c 的包中 放了p[i]之后 还能放的物品的价值。
i 从 1 到 n 。 dp[c-p[n]] 是放了 第n个物品后 还能放多少价值的物品。。。所以 P[n] 的M 值应该最大
通俗的说： 这个dp过程 正好是逆向的 。 dp[c-p[i]]是dp[c]的最优子状态。
所以 在DP 的时候我们应该按照 M的值从小到大排序。
也就是说我们应该按照 Q-P 的值 从小到 大排序在 DP 了。。。。
好了 结束。。。。。
附上本人的 代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct item {
int p;
int q;
int v;
bool operator < (const item b)const {
return q-p<b.q-b.p;
}
} tm[520];
int max(int a,int b ){
return (a>b)?a:b;
}
int n , m;
int dp[5200];
void init(){
for(int i=0;i<=m;i++){
dp[i]=0 ;
}
}
int main(){
while( scanf("%d%d",&n,&m)!=EOF){
for(int i =1;i<=n;i++){
int pi,qi,vi;
scanf("%d%d%d",&pi,&qi,&vi);
tm[i].p=pi;
tm[i].q=qi;
tm[i].v=vi;
}
sort(tm+1,tm+n+1);
init();
for(int i=1;i<=n;i++){
int p = tm[i].p;
int q = tm[i].q;
int v = tm[i].v;
for(int c = m;c>=q;c--){
dp[c]=max(dp[c],dp[c-p]+v);
}
}
cout << dp[m]<<endl;
}
return 0;
}