动态规划-硬币问题

发表于： 分类于：
字数： 936 阅读：≈ 2分钟 浏览：

算法思想：动态规划

实际问题：硬币问题

编写语言：Java

问题描述

假设有 1 元，3 元，5 元的硬币若干（无限），现在需要凑出 n 元。问如何组合才能使硬币的数量最少？

关键特征

要推出问题的关键特征与递归关系，必要的例子是少不了的。

我们先假设一个函数 d(i) 来表示需要凑出 i 的总价值需要的最少硬币数量，那么：

  1. 当 i = 0 时，很显然我们可以知道 d(0) = 0。因为不要凑钱了嘛，当然也不需要任何硬币了。注意这是很重要的一步，其后所有的结果都从这一步延伸开来。
  2. 当 i = 1 时，因为我们有 1 元的硬币，所以直接在第 1 步的基础上，加上 1 个 1 元硬币，得出 d(1) = 1。
  3. 当 i = 2 时，因为我们并没有 2 元的硬币，所以只能拿 1 元的硬币来凑。在第 2 步的基础上，加上 1 个 1 元硬币，得出 d(2) = 2。
  4. 当 i = 3 时，我们可以在第 3 步的基础上加上 1 个 1 元硬币，得到 3 这个结果。但其实我们有 3 元硬币，所以这一步的最优结果不是建立在第 3 步的结果上得来的，而是应该建立在第 1 步上，加上 1 个 3 元硬币，得到 d(3) = 1。
  5. 接着就不再举例了，推导过程和上面一样。

递归结构

我们来分析一下上述过程。可以看出，除了第 1 步这个看似基本的公理外，其他往后的结果都是建立在它之前得到的某一步的最优解上，加上 1 个硬币得到。即：d(i) = d(j) + 1，此处 j < i，但是在上述例子中我们发现 i = 3 时，有两个解，但我们选择了第二个解，即：** d(i) = min(d(j) + 1) **

有了结构，思路就清晰了，代码写起来也就很方便了。

Java代码 

//以下例子中 n 的数值取 11
public class CoinProblem
{
    public static void main(String[] args)
    {
        int[] coins = new int[]{1, 3, 5}; //硬币的面值
        int money = 11; //待求取的目标数额
        
        int[] result = getLeastCoins(coins, money);
        
        System.out.print("硬币的面值为：");
        for(int i = 0; i < coins.length; i++)
        {
            System.out.print(coins[i] + " ");
        }
        System.out.println();
        
        for(int i = 0; i < result.length; i++)
        {
            System.out.println("要凑齐数额 " + i + " 最少需要 " 
                + result[i] + " 个硬币");
        }
    }
    
    /**
      * param coins 存储硬币面值的数组
      * param money 待求取的目标数额
      * return result 存储各个数额所需最少硬币的数组
    */
    public static int[] getLeastCoins(int[] coins, int money)
    {
        int[] result = new int[money + 1];
        result[0] = 0; //数额0只需0个便可凑齐
        for(int i = 1; i < result.length; i++)
            result[i] = 10000; //初始化时各个数额需要最大上限个硬币
        
        for(int i = 1; i <= money; i++)
        {
            for(int coin : coins)
            {
                if(coin <= i)
                {
                    int min = 10000; //存储中间结果的变量，初始化为最大硬币上限
                    min = result[i - coin] + 1;
                    if(result[i] > min)
                        result[i] = min;
                }
            }
        }
        
        return result;
    }
}

运行结果

结果示例