当前位置：编程学习 > C/C++ >>

九度教程第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");  
        }  
    }  
}