voip
风的方向
厚德致远,博学敦行!
posts - 52,comments - 21,trackbacks - 0

最少硬币问题

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

编程任务:
对于给定的1≤n≤10,硬币面值数组T和可以使用的各种面值的硬币个数数组Coins,以及钱数m,0≤m≤20001,编程计算找钱m的最少硬币数。

Input

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

Output

对于每组输入数据,输出一行,即计算出最少硬币数。问题无解时输出-1。

Sample Input

3
1 3
2 3
5 3
18

Sample Output

5
         动态规划题。
代码如下:
#include<cstdio>
int main()
{
    
int t[11],coins[11],c[11][20002];//c[i][j]前i种硬币找j块钱最少硬币数
    int i,j,n,m,k;
    
while(scanf("%d",&n)!=EOF)
    
{
        
for(i=1;i<=n;i++)
        
{
            scanf(
"%d %d",&t[i],&coins[i]);
        }

        scanf(
"%d",&m);
        
for(i=1;i<=n;i++)        //初始化
            for(j=0;j<=m;j++)
            
{
                
if(j==0)
                    c[i][j]
=0;
                
else if(i==1)  
                    
if(j%t[i]==0&&j/t[i]<=coins[i])
                        c[
1][j]=j/t[i];
                    
else
                        c[
1][j]=1000000;
                
else
                    c[i][j]
=1000000;
            }


        
for(i=2;i<=n;i++)        //构造c数组
            for(j=1;j<=m;j++)
                
for(k=0;k<=coins[i];k++)
                
{
                    
if(c[i][j]>(c[i-1][j-k*t[i]]+k)&&(j-k*t[i])>=0)
                            c[i][j]
=c[i-1][j-k*t[i]]+k;
                }

        
if(c[n][m]!=1000000)
        
{
            printf(
"%d\n",c[n][m]);
        }

        
else
            printf(
"-1\n");
    }

    
return 0;
}

题目地址:http://acm.nankai.edu.cn/p1132.html
posted on 2010-09-17 13:32 jince 阅读(3708) 评论(0)  编辑 收藏 引用 所属分类: Questions

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


哈哈哈哈哈哈