题目链接：https://vjudge.net/contest/103424#problem/J
转载于：https://www.bbsmax.com/A/RnJW16GRdq/
题目大意：
有n个商品m块钱，给出买每个商品所花费的钱P、钱包里需要至少Q才有资格买、商品的价值V。问你如何购买商品的价值最大。
解题分析：
考虑下面的例子：A：p1=5, q1=10, v1=5; B：p2=3, q2=5, v2=6; 如果先买物品A再买物品B的话我至少需要10元钱，也就是money >= p1+q2,如果先买物品B再买物品A的话，我们至少需要13元钱，也就是money >= p2+q1。得到相同的价值的物品，我们却需要两个不同价值的钱，当然我们选择要花少的钱购买相同价值的商品了！
所以应使p1+q2 < p2+q1,交换位置p1-q1 < p2 - q2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node{
int p,q,v;
};
bool cmp(Node x,Node y)
{
return (x.q - x.p) < (y.q - y.p);
}
int main()
{
int N,M;
while (~scanf("%d%d",&N,&M))
{
Node node[];
int dp[];
memset(dp,,sizeof(dp));
memset(node,,sizeof(node));
for (int i = ;i < N;i++)
{
scanf("%d%d%d",&node[i].p,&node[i].q,&node[i].v);
}
sort(node,node+N,cmp);
for(int i = ;i < N;i++)
{
for (int j = M;j >= node[i].q;j--)
{
dp[j] = max(dp[j-node[i].p] + node[i].v,dp[j]);
}
}
printf("%d\n",dp[M]);
}
return ;
}
2018-05-13