当前位置:编程学习 > JAVA >>

动态规划法求解硬币找零(Java)

算法描述:
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。基本思想也是将待求解问题分解成若干个子问题,先求解子问题,并将子问题的结果保存下来,然后从这些子问题的解得到原问题的解。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。
问题描述:
现存在一堆面值为 V1、V2、V3 … 个单位的硬币,问最少需要多少个硬币才能找出总值为 T 个单位的零钱?
解题思路:
1,找出面值最接近T的硬币V  www.zzzyk.com
2,将f(T)问题的求解转换成f(T-V)+1问题的求解,以此出现递归
代码实现:
CoinChange类用于处理硬币找零的业务:
[java] 
public class CoinChange { 
    /**
     * 获取找零硬币个数
     * @param coinValue 硬币的面值  
     * @param totalValue 需要找零的钱数
     * @return
     */ 
    public int coinNum(int[] coinValue,int totalValue){ 
        List<Integer> coins=new ArrayList<Integer>(); 
        coins.add(0); 
        for(int i=1;i<=totalValue;i++){ 
            int coin=nearestCoin(i,coinValue); 
            int coinNum=coins.get(i-coin)+1; 
            coins.add(coinNum); 
        } 
        return coins.get(totalValue); 
    } 
    /**
     * 获取最接近找零钱数的硬币面值
     */ 
    private int nearestCoin(int value,int[] coinValues){ 
        int res=0; 
        int nearest=Integer.MAX_VALUE; 
        for(int coinValue:coinValues){ 
            if(coinValue<=value){ 
                int distance=value-coinValue; 
                if(distance<nearest){ 
                    nearest=distance; 
                    res=coinValue; 
                } 
            } 
        } 
        return res; 
    } 

Main类用于测试:
[java]
public class Main { 
    public static void main(String[] args) { 
        CoinChange coinChange=new CoinChange(); 
        int res=coinChange.coinNum(new int[]{1,2,3,5,11},81); 
        System.out.println(res); 
    } 

打印输出:9
补充:软件开发 , Java ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,