题意是： 给你一些钱 m ，然后在这个国家买东西， 共有 n 件物品，每件物品有 价格 P 价值 V 还有一个很特别的属性 Q, Q 指 你如过想买这件物品 你的手中至少有这钱Q 。 虽然你只要花费 钱P ，但你的手中至少有钱Q，如果不足Q ，不能买。问给你钱M ，列出N件物品，最多能获得多少价值的东西。。。。
这道题如果没有Q的限制的话就是一道01背包的水题，但是加上了Q的限制这就是一道考察对DP的深刻理解的题目了，好多题解上说按照p-q从大到小排序即可，但是至于为什么并没有说透，所以今天总结一下。
一个问题无论是DP，还是贪心求解，需要满足一个无后效性，其中所谓的无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。就是说我在当前状态做转移的时候，前面的所有的状态都已经枚举过了，只不过只保留下来了最优解，但是抵达当前状态路径不唯一，仅是最终最优结果唯一。
不考虑q的限制的01背包的状态转移方程是d[j] = max(d[j],d[j--p[i]]+v[i]);显然j状态实际上是从d[i-1][j]和d[i-1][j-p[i]]转移过来的。（这里我用了滚动数组）那么什么时候可以转移呢？j-p[i]是这个状态的花费，那么m-（j-p[i]）是当前我所剩下的钱，只有当m-（j-p[i]) > q[i]的时候，才能转移.
整理一下就p[i] <= j <=m+ p[i] - q[i];即可以更新的区间是（p[i],m+q[i] - p[i])所谓无后效性是指，前面的在更新时对后面的决策无影响。那么后面的d[j-p[i]]这个状态肯定在前面已经更新到了。所以就是说前面的更新的范围应该比后面大。所以就是p1 - q1 > p2-q2;即按照p-q从大到小排序,或者q - p按照从小到大排序才能保证后面的能更新到不丢失状态。
AC代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <stack>
#define N 100005
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define lc rt<<1
#define rc rt<<1|1
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = ;
const int mod = ;
typedef long long ll; int n,m;
struct node
{
int p,q,v;
bool operator < (const node& r)const
{
return q - p < r.q - r.p;
}
}a[maxn]; int d[maxn]; int main()
{
//freopen("in","r",stdin);
while(~scanf("%d%d",&n,&m)) {
for(int i = ; i <= n; ++i) {
scanf("%d%d%d",&a[i].p, &a[i].q,&a[i].v);
}
sort(a+,a+n+);
memset(d,,sizeof(d));
int mx = ;
for(int i = ; i <= n; ++i)
{
for(int j = m; j >= a[i].q; --j)
{
d[j] = max(d[j],d[j - a[i].p] + a[i].v);
}
}
printf("%d\n",d[m]);
}
}