一、贪心算法
例子
假设有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
三、贪心算法与动态规划的区别
（1）贪心是求局部最优，但不定是全局最优。若想全局最优，必须证明。
dp是通过一些状态来描述一些子问题，然后通过状态之间的转移来求解。般只要转移方程是正确的，答案必然是正确的。
（2）动态规划本质上是穷举法，只是不重复计算罢了。结果是最优的。复杂度高。
贪心算法不一定最优。复杂度一般较低。
（3）贪心只选择当前最有利的，不考虑这步选择对以后的选择造成的影响，眼光短浅，不能看出全局最优；动规是通过较小规模的局部最优解一步步最终得出全局最优解。
（4）从推导过程来看，动态规划是贪心的泛化，贪心是动态规划的特例
加入少儿信息学奥赛学习QQ群请扫左侧二维码，关注微信公众号请扫右侧二维码
QQ群和公众号.png
网友评论