九度教程第102題

C語言源碼： [cpp]   #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");           }       }   }