HDU - 3466 Proud Merchants

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=3466

题目大意：

思路：
其实，就是让C商品的q不等于p，其他都相同，这时，你就会发现如果要买C商品的话，肯定得先买C商品，因为买C商品的代价最大。所以，我们可以按照qi-pi的顺序来确定大顺序。这里我们还可以用更严谨的方式来证明一下，比如A:p1 q1, B:p2 q2，然后，假设单独买A或者B的话，都是可以买到的。这时，若先买A，则你至少需要p1+q2的钱；若先买B，则至少需要p2+q1的钱。那肯定是花最少的钱咯，所以如果先买A再买B，那么p1+q2<p2+q1，转换一下，就是q1-p1>q2-p2，也就是说qi-pi大的先买。这里还得注意一点就是，排序的时候，得按照qi-pi从小到大排序，因为你买第n件商品的时候，是在比较你是否要先买第n件商品。打个比方让大家更好地理解，比如说f(3, 10)，是不是max(f(2, 10-p3)+v3, f(2, 10))，你会发现这个第一种情况f(2,10-p3)+v3中，是先买了第三件商品，也就是说排在后面的商品会先买。好的，排好序之后，就把问题就转换为不需要考虑顺序的问题了，那就是解决0/1背包问题了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;
const int N = 1010101;
struct thing
{
    int w;
    int q;
    int v;
}things[N];
bool cdx(thing a,thing b)
{
    return (a.q-a.w)<(b.q-b.w);//这返回值有点离谱有空学一下结构体
}
int dp[N];
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m) != EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i = 1;i <= n ;i ++) scanf("%d%d%d",&things[i].w,&things[i].q,&things[i].v);
        sort(things + 1,things + 1 + n,cdx);
        for(int i = 1;i <= n;i ++)
            for(int j = m;j >= things[i].q;j --)//买东西身上的钱要大于商人要求的钱数
        {
            dp[j] = max(dp[j],dp[j - things[i].w] + things[i].v);//花费的还是商人的物品价格 和要求身上的钱数无关
        }
        printf("%d\n",dp[m]);
    }
}