学步园

01背包，我不敢说这道题目简单，因为如果让我没接触动态规划前自己想是很有难度的。 参看《背包九讲》第一讲。
我说下应该如何想出这个问题的思路的，而不是这道题目的思路。遇到这个问题后先从整个问题考虑有没有合适的方法，如果没有就应该知道，问题整体无法解决，就看看子问题能否分解成子问题，通过解决子问题来解决整个问题。 这道题目可以想到把N件物品放入容量为V的背包分解成将前i件物品放到容量为V的背包中，分解后的子问题应该如何解决呢？看看能不能提取出只涉及一个物品的问题，还有子问题解决后怎么能解决整个问题呢？就会想到如果只考虑第i件物品，问题又会转化为“前i-1件物品放入容量为V的背包中”，然后就考虑第i件物品放不放，想到这里dp的状态转移就容易想出来了。

#include <iostream>
#include <string>
#define MAX 3500
#define MAX_W 12885
using namespace std;

int W[MAX], D[MAX], dp[MAX_W];
int N, M;

int main()
{
	while(scanf("%d%d", &N, &M) != EOF)
	{
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= N; i++)
		{
			scanf("%d%d", &W[i], &D[i]);
		}
		for(int i = 1; i <= N; i++)
		{
			for(int j = M; j >= W[i]; j--)
			{
		     	dp[j] = max(dp[j], dp[j - W[i]] + D[i]);
			}
		}
		printf("%d\n", dp[M]);
	}
	return 0;
}