最少硬币数——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);
    }
}