贪心算法与动态规划贪心法的基本思路
贪心法和动态规划法的区别
动态规划和贪心算法都是递归算法，都是利用局部最优解推导出全局最优解
不同之处：
贪心算法：
1、在贪心算法中，每一步做出的贪心决策是不能改变的，因为贪心策略是从上一步的最优解中推导出下一步的最优解，不会保留上一步之前的最优解.
2、由（1）的介绍可知，贪心法的正确条件是：每一步的最优解必须包含上一步的最优解。
动态规划算法：
1.全局最优解必然包含一个局部最优解，但不一定包含之前的局部最优解，所以需要记录之前所有的最优解
2、动态规划的关键是状态转移方程，即如何从得到的局部最优解推导出全局最优解
3.边界条件：最简单的，可以直接得到的局部最优解
================================================ == ==============================
贪心算法和动态规划
贪心法的基本思想：
它从问题的初始解开始，逐渐逼近给定的目标，以尽快获得更好的解。 当达到算法中的某个步骤并且无法进一步前进时，算法将停止。
这个算法有一个问题：
1、不保证最终得到的解就是最好的；
2、不能用来求问题的最大解或最小解；
3. 只能找到满足一定约束条件的可行解范围。 算法实现过程：
从问题的初步解决方案开始；
while 可以朝着给定的总体目标迈出一步
求一个可行解的解元；
由所有解元素组成的问题的可行解
贪心算法最经典的例子就是金钱问题。
比如中国的货币只看元，有1元、2元、5元、10元、20、50、100
我要16元，16个1元，8个2元，怎么能少呢？
如果我用贪心计算，那是我每次拿那张牌能得到的最大的。
比如16，我第一次买不起20，我拿10块，OK，还有6块，再拿5块，剩下的1块
即三个10、5、1。
每次你拿走你能拿走的最大的东西，那就是贪婪。
但是一定要注意，贪心不是最优解，也就是说使用贪心不一定是张数最少
贪心只能得到更好的解，贪心算法容易得到。
再次注意，为什么我们可以贪图金钱？ 因为我们国家的钱币大小的设计正好可以让贪心算法计算出最优解（一般一个国家的硬币都是这样设计的），如果不这样设计就不一样了
例如，某国的硬币分为1元、3元和4元。
想拿6元怎么拿？贪心的话先拿4再拿两个1，一共3个币
什么才是最好的？两个3元就够了
寻找最优解的问题从根本上说是对解空间的遍历。 最直接的暴力分析很容易得到，而最优解的解空间通常呈指数增长，因此暴力穷竭是不可行的。
绝大部分最优解问题都可以拆分成一个个子问题。 将解空间的遍历看作是对子问题树的遍历，以某种形式遍历整棵树就可以得到最优解。 如上所述，这是不可行的。
贪心和动态规划本质上是对子问题树的剪枝。 两种算法都要求问题具有的一个属性是“子问题最优性”。 即构成最优解的每个子问题的解对于子问题本身也一定是最优的。 如果我们以自上而下的方向（原问题为根）看问题树，每次只需要向下遍历代表最优解的子树，就可以保证得到全局最优解。 更形象地说，你可以简单地用一个值（最优值）来表示整个子树，而不用去寻找这棵子树可能表示的所有值。
动态规划方法代表了此类问题的一般解决方案。 我们自下而上（从叶子到根）构建子问题的解贪心法与动态规划方法的异点，对于每个子树的根，求下面每个叶子的值，取最优值作为自己的值，丢弃其他值。 动态规划的成本取决于选项的数量（树中叉子的数量）和子问题的数量（树中节点的数量，或者树的高度？）。
贪心算法是动态规划方法的一个特例。 贪心比较特殊，可以证明每棵子树根的值不依赖于下面叶子的值，而只依赖于当前问题的状态。 换句话说，您可以在不知道节点的所有子树的情况下找到节点的值。 通常这个值是当前问题情况的明显“最佳”情况。 因此，用“贪心”来形容这个算法的本质。 由于贪心算法的这一特性，它不需要自下而上遍历解空间树，而只需要从根开始，选择最优路径，一路走到尽头。 因此，与动态规划相比，它的成本只取决于子问题的数量，而选择的数量始终为 1。
------------------------------
找钱的问题很大程度上可以帮助我们理解动态规划法式贪心算法的区别
二、问题
现在的人民币只有面值11元、5元和1元三种。
给定一个编号为money的人民币，如何用这三种面额的人民币求出来，用最少的人民币张数
例如：给定10元，我们可以找到以下方法：
2 5元面额
1面额5元+5面额1元
10张1元面额
我们选择第一种方式查找。 只用两块钱。
3.分析
可以使用动态规划找到最佳解决方案。
使用贪心算法可以找到最优解（当问题满足贪心选择性质时。换钱问题不满足11、5、1三种面额情况下的性质）
或者求一个近似最优解（本题设置的三种面额情况就是这样）
如果你现在想换15元，那么
1.根据动态规划法的解题思路，最优解为3张5元面额，共3张
2.根据贪心算法的解题思路，得到的近似最优解为1面额11元加4面额1元，共5面额
从这里可以大致看出两者的区别
4.代码实现找钱问题的动态规划方法和贪心算法，形成对比
查看？
01./************************************************* * ***********
02. *问题：最小面值11 5 1的人民币有3种，张数最少的换钱
03. *说明：动态规划和贪心算法求解问题的比较
04. *作者：
05. *************************************************** * ************/
06.#
07.#N 4
08.#11 // 面额为11元的人民币（可修改）
09.#5 // 面额为5元的人民币（可修改）
10.# 1 //面额为1元的RMB（不要修改，否则可能找不到）
11.# 1000 //可开仓金额上限
12.
13./***************************动态规划法****************** ******************
14. *方法：
15.*整数[]； //Num[i] 保存找到i元所需的最少人民币张数
16.*整数[N][]； //[i][j]表示寻找j元，需要面值的人民币张数
17.*
18. * Num[i] = i; 0= ){
94.[2]++；
95.我-=；
96. 总计++；
97.}
98.否则如果（我>=）{
99.[3]++；
100.我-=；
101.总计++；
102.}
103.否则{
104. }
105.}
106. 总计；
107.}
108.无效主（）{
109. //测试动态规划方法
110./* 诠释我；
111. int money = 23;
112. 整数[]; //Num[i] 保存开i元最少需要的人民币张数
113. 整数[N][]； //[i][j]表示寻找j元，需要面值的人民币张数
114. ("%d\n",(money,Num));
115. ("----------------------------------------\n" );
116.（金钱，数字，）；
117. ("-------------------------------------------- \n" );
118. 对于（我=0；我
九软件 版权声明：以上发布的内容及图片均来源于网络，如有无意侵犯到您的权利，请联系我们及时删除！
