最少硬币数——Java

2019-10-25 07:06:36来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

最少硬币数——Java

问题:有n种硬币,面值分别为v1,v2,v3,…,vn,存于数组T〔1:n〕中,可以使用的各种面值的硬币个数存于数组Coins〔1:n〕中。对任意钱数0≤m≤20001,设计一个用最少硬币找钱m的方法。

 

 数据输入:   第一行中只有1 个整数给出n的值

      第2 行起每行2 个数,分别是T[j]和Coins[j]

      最后1 行是要找的钱数m

 

 结果输出: 程序运行结束时,将计算出的最少硬币数。

     问题无解时输出-1。

Input

3

1 3

2 3

5 3

18

output

5

本题选用动态规划算法,代码如下:

import java.util.Scanner;
public class coins {
    public static void FindMinCoins(int n,int[] values,int[]valuescounts,int money,int[] coinUsed){
        for(int i=1;i<=money;i++)
            coinUsed[i]=999;//给每种面值所需硬币数初始化一个很大的数值。当最后如果得出的结果是这个数时,说明凑不出来
        //遍历硬币面额数组,找到前边所能找到的最小硬币数加1
        for(int i=0;i<n;i++) {
            for(int j=0;j<valuescounts[i];j++) {
                for(int k=money;k>=values[i];k--) {
                    int temp=coinUsed[k-values[i]]+1;
                    /*找到几种情况中最小的硬币数 如使用1、2、5元 凑18元:
                     * 先用1元凑coinUsed[18-1]+1、
                     * 先用2元凑coinUsed[18-2]+1、
                     * 先用5元凑coinUsed[18-5]+1
                     */
                    if(temp<coinUsed[k])
                        coinUsed[k]=temp;
                }
            }
        }
        if(coinUsed[money]==999)//若面值所需硬币数还是初始化值,说明在输入的条件下凑不出来
            System.out.println("-1");
        else
            System.out.println(coinUsed[money]);
    }      
          

    public static void main(String[] args) {      
        Scanner input=new Scanner(System.in);
        int n;//硬币面值的种类数
        n=input.nextInt();
        int[]T=new int[n];//T用来保存硬币面值
        int[]Coins=new int[n];//Coins用来保存每种硬币的个数
        for(int i=0;i<n;i++)
        {
              T[i]=input.nextInt();
              Coins[i]=input.nextInt();
        }
        // 需要找零的面值      
        int money = input.nextInt();      
        // 保存每一个面值找零所需的最小硬币数,0号单元舍弃不用,所以要多加1      
        int[] coinsUsed = new int[money + 1]; 
        FindMinCoins(n,T,Coins,money,coinsUsed);
    }
}
View Code

 


原文链接:https://www.cnblogs.com/Small-Windmill/p/11731948.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java连载44-静态代码块、实例代码块、继承

下一篇:Spring Boot 配置元数据指南