Proud Merchants 背包

Proud Merchants
原题链接https://vjudge.net/contest/348156#problem/I


题目大概为给你一定的钱 然后购买商品最大值
基本为01背包 不过跟01背包相比增加了一部分限制
假如你需要购买p1的商品 你需要拥有p2的钱商人才会卖给你
这个时候就需要在装入背包同时要可以装入的更多才行，
PS
第一个商品 p1 p2
第二个商品 q1 q2
当你需要装入两个商品时 你所需要的钱是第一个商品花费的p1以及购买第二个商品的的条件q2的和，也就是p2+q1;另一种情况为先买第二个商品也就是q2+p1;对于两种情况我们需要选择较小的一种，也就是p2+q1<q2+p1时；先买第一个商品 p2-p1<q2-q1时 我们先购买第一个商品
所以我们需要对所有商品进行排序 对于满足p2-p1更小的商品优先选择

#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
using namespace std;
struct node
{
	long long pi;
	long long qi;
	long long vi;
} stu[10005];
bool cmp(node x,node y)//排序
{
	return (x.qi-x.pi)<(y.qi-y.pi);
}
long long dp[100005];
int main()
{
	long long n,m;
	while(~scanf("%lld %lld",&n,&m))
	{
		long long i,j;
		for(i=1; i<=n; i++)
		{
			scanf("%lld %lld %lld",&stu[i].pi,&stu[i].qi,&stu[i].vi);
		}
		sort(stu+1,stu+1+n,cmp);
	/*	for(i=1;i<=m;i++)
		{
			dp[i]=0;
		}*/
		memset(dp,0,sizeof(dp));
		/*	for(i=1;i<=n;i++)
			{
				printf("***%lld %lld\n",stu[i].pi,stu[i].qi);
			}*/
		for(i=1; i<=n; i++)
		{
			for(j=m; j>=stu[i].qi; j--)//注意背包中可以装入商品的条件 身上的钱要大于商人要求的钱
			{
				dp[j]=max(dp[j],dp[j-stu[i].pi]+stu[i].vi);//购买商品时要减去购买商品所需的钱与商人要求拥有的钱无关
			}
		}
		printf("%lld\n",dp[m]);
	}
	return 0;
}