题目链接：【hdu 3466】
这题的核心部分就是这样子的
<span style="font-size:14px;">for(int i=0; i<n; i++)
{
for(int j=m; j>=h[i].q; j--)
{
dp[j]=max(dp[j], dp[j-h[i].p]+h[i].v);
}
}</span>
令x1 = q1-p1 x2 = q2-p2，假设一开始没有排序，按输入的顺序操作，那肯定是先买1号商品，再买2号商品
如果x1 > q2，那先买1号再买2号肯定会出错，因为对于1号来说，dp[j]中j的范围是q1~m， 对于2号来说，dp[j]中的j的范围是q2~m，显然2号的某些dp值是会影响到1号的，所以要先买2号，再买1号
其他情况下1号2号的先后顺序并不影响结果
又因为q必定大于x，所以我们可以先按x来排序，从小到大排，x越大的要越往后，这样才能保证用m元钱买尽可能多的价值
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
int dp[5010];
struct node
{
int p, q, v, x;
friend bool operator < (const node n1, const node n2)
{
return n1.x<n2.x;
}
}h[510];
int main()
{
int n, m;
while(~scanf("%d%d", &n, &m))
{
memset(dp, 0, sizeof(dp));
for(int i=0; i<n ;i++)
{
scanf("%d%d%d", &h[i].p, &h[i].q, &h[i].v);
h[i].x=h[i].q-h[i].p;
}
sort(h, h+n);
for(int i=0; i<n; i++)
{
for(int j=m; j>=h[i].q; j--)
{
dp[j]=max(dp[j], dp[j-h[i].p]+h[i].v);
}
}
printf("%d\n", dp[m]);
}
return 0;
}