9度教程第102题

题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=101

C语言源码：

#include<stdio.h>
#include<limits.h>
#define maxsize 10005
int dp[maxsize];
typedef struct coin
{
	int weight;
	int worth;
}coin;
coin a[505];
int min(int a,int b)
{
	return a<b?a:b;
}
int main()
{
	int t,e,f,w,n,i,j;
	while(scanf("%d",&t)!=EOF)
	{
		while(t--)
		{
			scanf("%d %d",&e,&f);
			w=f-e;
			scanf("%d",&n);
			for(i=1;i<=n;i++)
				scanf("%d %d",&a[i].worth,&a[i].weight);
			for(i=1;i<maxsize;i++)
				dp[i]=INT_MAX;
			dp[0]=0;
			for(i=1;i<=n;i++)
				for(j=a[i].weight;j<=w;j++)
					if(dp[j-a[i].weight]!=INT_MAX)
						dp[j]=min(dp[j],dp[j-a[i].weight]+a[i].worth);
			if(dp[w]!=INT_MAX)
				printf("The minimum amount of money in the piggy-bank is %d.\n",dp[w]);
			else
				printf("This is impossible.\n");
		}
	}
}