一、贪心算法

例子

假设有1元，5元，11元这三种面值的硬币，给定一个整数金额，比如28元，最少使用的硬币组合是什么？

分析

碰到这种问题，咱们很自然会想起先用最大的面值，再用次大的面值……这样得到的结果为两个11元，一个5元，一个1元，总共是四个硬币。

C语言实现

#include<stdio.h>

void greed(int m[],int k,int total);

int main(void)
{
    int money[] = {11, 5, 1};
    int n;
    n = sizeof(money)/sizeof(money[0]);
    greed(money, n, 28);

    return 0;
}

/*
*  m[]:存放可供找零的面值，降序排列
*  k:可供找零的面值种类数
*  total:需要的总金额
*/
void greed(int m[],int n,int total)
{
    int i;
    for(i = 0; i < n; i++)
    {
      while(total >= m[i])
      {
          printf("%d ", m[i]);
          total -= m[i];
      }
    }
}

运行结果：

11 11 5 1

思想

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

不足

上面的例子，total = 28，得到的“11 11 5 1”恰巧是最优解。
假如total = 15呢？
total = 15时，结果为“11 1 1 1 1”，共用了五枚硬币。但是这只能算是较优解，不是最优解。因为最优解是“5 5 5”，共三枚硬币。
所以贪心算法只能保证局部最优（第一枚11就是局部最优），不能保证全局最优。

二、动态规划算法

咱们仍以15为例，换一种思路，看看如何得到最优解。
（1）面值为1时，最少需要一个一元硬币

（2）面值为2时，最少需要两个一元硬币

（3）面值为3时，最少需要三个一元硬币

（4）面值为4时，最少需要四个一元硬币

（5）面值为5时，有两个方案:
① 在面值为4的基础上加一个1元的硬币，需要五个硬币
② 挑一个面值为5元的硬币，需要一个硬币
取最小值，需要一个硬币

（6）面值为6时，两个方案：
① 比1元（一个硬币）多了5元（一个硬币），需要两个硬币
② 比5元（一个硬币）多了1元（一个硬币），需要两个硬币
取最小值，需要两个硬币

（7）面值为7时，两个方案：
① 比1元（一个硬币）多了6元（两个硬币），需要三个硬币
② 比5元（一个硬币）多了2元（两个硬币），需要三个硬币
取最小值，需要三个硬币

（8）面值为8时，两个方案：
① 比1元（一个硬币）多了7元（三个硬币），需要四个硬币
② 比5元（一个硬币）多了3元（三个硬币），需要四个硬币
取最小值，需要四个硬币

（9）面值为9时，两个方案：
① 比1元（一个硬币）多了8元（四个硬币），需要五个硬币
② 比5元（一个硬币）多了4元（四个硬币），需要五个硬币
取最小值，需要五个硬币

（10）面值为10时，两个方案：
① 比1元（一个硬币）多了9元（五个硬币），需要六个硬币
② 比5元（一个硬币）多了5元（一个硬币），需要两个硬币
取最小值，需要两个硬币

（11）面值为11时，三个方案：
① 比1元（一个硬币）多了10元（两个硬币），需要三个硬币
② 比5元（一个硬币）多了6元（两个硬币），需要三个硬币
③ 取面值为11元的硬币，需要一个硬币
取最小值，需要一个硬币

（12）面值为12时，三个方案：
① 比1元（一个硬币）多了11元（一个硬币），需要两个硬币
② 比5元（一个硬币）多了7元（三个硬币），需要四个硬币
③ 比11元（一个硬币）多了1元（一个硬币），需要两个硬币
取最小值，需要两个硬币

（13）面值为13时，三个方案：
① 比1元（一个硬币）多了12元（两个硬币），需要三个硬币
② 比5元（一个硬币）多了8元（四个硬币），需要五个硬币
③ 比11元（一个硬币）多了2元（两个硬币），需要三个硬币
取最小值，需要三个硬币

（14）面值为14时，三个方案：
① 比1元（一个硬币）多了13元（三个硬币），需要四个硬币
② 比5元（一个硬币）多了9元（五个硬币），需要六个硬币
③ 比11元（一个硬币）多了3元（三个硬币），需要四个硬币
取最小值，需要四个硬币

（15）面值为15时，三个方案：
① 比1元（一个硬币）多了14元（四个硬币），需要五个硬币
② 比5元（一个硬币）多了10元（两个硬币），需要三个硬币
③ 比11元（一个硬币）多了4元（四个硬币），需要五个硬币
取最小值，需要三个硬币

最终，得到的最小硬币数是3。并且从推导过程可以看出，计算一个数额的最少硬币数，比如15，必须把它前面的所有数额（1~14）的最少硬币数都计算出来。这够成了一个递推（注意不是递归）的过程。

上述推导过程的Java实现：

public class CoinDP {

    /**  
     * 动态规划算法  
     * @param values:    保存所有币值的数组  
     * @param money:     金额  
     * @param minCoins:  保存所有金额所需的最小硬币数 
     */ 
    public static void dp(int[] values, int money, int[] minCoins) {  

        int valueKinds = values.length;
        minCoins[0] = 0;
        
        // 保存1元、2元、3元、……、money元所需的最小硬币数  
        for (int sum = 1; sum <= money; sum++) {  

            // 使用最小币值，需要的硬币数量是最多的
            int min = sum;  

            // 遍历每一种面值的硬币
            for (int kind = 0; kind < valueKinds; kind++) {               
                // 若当前面值的硬币小于总额则分解问题并查表  
                if (values[kind] <= sum) {  
                    int temp = minCoins[sum - values[kind]] + 1;  
                    if (temp < min) {  
                        min = temp;  
                    }  
                }  else {
                    break;
                }
            } 
            
            // 保存最小硬币数  
            minCoins[sum] = min;  

            System.out.println("面值为 " + sum + " 的最小硬币数 : " + minCoins[sum]);  
        }  
    }  

    public static void main(String[] args) {  

        // 硬币面值预先已经按升序排列
        int[] coinValue = new int[] {1,5,11};  
        
        // 需要的金额(15用动态规划得到的是3（5+5+5），用贪心得到的是5（11+1+1+1+1）
        int money = 15;  
        
        // 保存每一个金额所需的最小硬币数，0号单元舍弃不用，所以要多加1  
        int[] coinsUsed = new int[money + 1];  

        dp(coinValue, money, coinsUsed);  
    }  
}

运行结果：

面值为1的最小硬币数：1
面值为2的最小硬币数：2
面值为3的最小硬币数：3
面值为4的最小硬币数：4
面值为5的最小硬币数：1
面值为6的最小硬币数：2
面值为7的最小硬币数：3
面值为8的最小硬币数：4
面值为9的最小硬币数：5
面值为10的最小硬币数：2
面值为11的最小硬币数：1
面值为12的最小硬币数：2
面值为13的最小硬币数：3
面值为14的最小硬币数：4
面值为15的最小硬币数：3