最少硬币问题

最少硬币问题

时间: 1ms        内存:64M

描述:

设有n种不同面值的硬币,各硬币的面值存于数组T[1:n]中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数存于数组Coins[1:n]中。
对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,计算找钱m的最少硬币数。

输入:

输入数据第一行中只有1个整数给出n的值,第2行起每行2个数,分别是 T[j]和Coins[j]。最后1行是要找的钱数m。

输出:

输出数据只有一个整数,表示计算出的最少硬币数。问题无解时输出-1。

示例输入:

3
1 3
2 3
5 3
18

示例输出:

5

提示:

参考答案(内存最优[828]):

#include<stdio.h>
#include<stdlib.h>  
#include<string.h>  
int ans[20005];  
int t[12],coin[12];  
int main()  
{  
    int n,sum,i,j,k;  
    scanf("%d",&n); 
    for(i=0;i<n;i++)  
        scanf("%d%d",&t[i],&coin[i]);  
    scanf("%d",&sum);  
    memset(ans,-1,sizeof(ans));  
    ans[0]=0;  
    for(i=0;i<n;i++)  
    {  
        for(k=sum;k>=0;k--)  
        {  
            if(ans[k]>=0)  
            {  
                for(j=1;j<=coin[i]&&(k+j*t[i])<=sum;j++)  
                {  
                    if(ans[k+j*t[i]]>ans[k]+j||ans[k+j*t[i]]<0)
						ans[k+j*t[i]]=ans[k]+j;  
                }  
            }  
        }  
    }  
    printf("%d\n",ans[sum]);  
    return 0;  
} 

参考答案(时间最优[16]):

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int ans[20005];
int t[12],coin[12];
int main()
{
    int n,sum,i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%d%d",&t[i],&coin[i]);
    scanf("%d",&sum);
    memset(ans,-1,sizeof(ans));
    ans[0]=0;
    for(i=0;i<n;i++)
    {
        for(k=sum;k>=0;k--)
        {
            if(ans[k]>=0)
            {
                for(j=1;j<=coin[i]&&(k+j*t[i])<=sum;j++)
                {
                    if(ans[k+j*t[i]]>ans[k]+j||ans[k+j*t[i]]<0)
						ans[k+j*t[i]]=ans[k]+j;
                }
            }
        }
    }
    printf("%d\n",ans[sum]);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注