动态规划——有顺序的背包问题

HUD 3466
Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?
input：
There are several test cases in the input.

Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.

The input terminates by end of file marker.
output：
For each test case, output one integer, indicating maximum value iSea could get.
Sample Input
2 10
10 15 10
5 10 5
3 10
5 10 5
3 5 6
2 7 3
Sample Output
5
11
以前写背包问题是没有考虑过装东西的先后顺序的，这题由于那个奇怪的商人，要装东西要有先后顺序。
我们假设买a b两样东西设其属性为
c1（cost）q1 v1
c2 q2 v2
先买a的话我们需要
c1 + q2 的钱
先买b的话我们需要
c2 + q1的钱
如果某两件商品要有买的顺序
假设一定要先买a
c1 + q2 > c2 + q1
即：c1 - q1 > c2 - q2
就是差值大的先买 ，我们用结构体排个序就行了
但是要注意，第二层循环是倒序，所以我们的排序要升序

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int dp[5007];
struct good
{
	int c, q, v;
	int f;
}a[507];
int n, m;
bool cmp(good x, good y)
{
	return x.f < y.f ;
}
int main()
{
	while(scanf("%d%d",&n, &m) != EOF)
	{
		memset(dp,0,sizeof(dp));
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i].c >> a[i].q >> a[i].v ;
			a[i].f = a[i].q - a[i].c;
		}
		sort(a+1, a+1+n, cmp);
		for(int i = 1; i <= n; i++)
		{
			for(int j = m; j >= a[i].q ; j--)
			{
				dp[j] = max(dp[j], dp[j-a[i].c ] + a[i].v );
			}
		}
		cout << dp[m] << endl;
	}
}