江苏龙网

  1. 首页 > 生活 > >

动态规划和贪心法的区别( 二 )

动态规划和贪心法的区别
时刻贪婪算法得到的最优行动与MDP得到的最优行动是一样的。如果上述结论对于对于任意 动态规划和贪心法的区别
都成立，那么两者的最优策略是相同的，贪婪算法得到的也自然是全局最优。

由于（1）是（3）的一个特例，所以上述结论可以很容易拓展到DP中。

■网友
如何理解动态规划？

■网友
小萌新试答打个比方，去吃饭贪心算法:随时补货的自助餐，而且你不会吃撑，那么疯狂吃能看见的最贵的就行。动态规划:你只知道点了什么菜，连上菜的顺序都不知道，所以要提前根据之后要上的菜和饱腹感规划，这道菜我吃不吃，吃了会怎么样，不吃会怎么样……总的来说贪心就像是理想化的动态规划，取最优解(包括整体最优解和当前最优解)方式固定且每次只需要取当前最优解。而动态规划就需要根据情况综合判断。
■网友
#一、贪心算法
###例子
假设有1元，5元，11元这三种面值的硬币，给定一个整数金额，比如28元，最少使用的硬币组合是什么？

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

###C语言实现
```
#include\u0026lt;stdio.h\u0026gt;

void greed(int m,int k,int n);

int main(void)
{
int money = {11, 5, 1};
int k;
k = sizeof(money)/sizeof(money);
greed(money, k, 28);

return 0;
}

/*
* m:存放可供找零的面值，降序排列
* k:可供找零的面值种类数
* n:需要找零数
*/
void greed(int m,int k,int total)
{
int i;
for(i = 0; i \u0026lt; k; i++)
{
while(total \u0026gt;= m \u0026amp;\u0026amp; total \u0026gt; 0)
{
printf("%d ", m);
total -= m;
}
}
}
```

运行结果：
```
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元（两个硬币），需要三个硬币


推荐阅读


上一篇：魔兽世界的兽人语、鱼人语是怎样设计出来的

下一篇：Apple Music上线半年付费用户1000万，是否可超越Spotify