rt.思路同第二篇题解，样例全过了WA on #6

代码如下：

#include"bits/stdc++.h"
using namespace std;
int dp[105][100005];
int price[105],reward[105];
int kinds,money,tot=0;
int main()
{
	scanf("%d%d",&kinds,&money);
	for (int i=1;i<=kinds;i++)
	{
		scanf("%d%d",&price[i],&reward[i]);
		tot+=reward[i];
	}
	dp[0][0]=0;
	for (int i=1;i<=tot;i++)
	{
		dp[0][i]=1919810;
	}
	for (int i=1;i<=kinds;i++)
	{
		for (int j=0;j<=tot;j++)
		{
			if (j>=reward[i])
			{
				dp[i][j]=min(dp[i-1][j],(dp[i-1][(j-reward[i])]+price[i]));
			}
			if (j<reward[i])
			{
				dp[i][j]=dp[i-1][j];
            }
		}
	}
	for (int i=tot;i>=0;i--)
	{
		if (dp[kinds][i]<=money)
		{
			printf("%d",i);
			return 0;
		}
	}
}