九度教程第102题
题目地址：http://jobdu.sinaapp.com/problem.php?cid=1040&pid=101
C语言源码：
#include<stdio.h>#include<limits.h>#define maxsize 10005int 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]);elseprintf("This is impossible.\n");}}}