贪心算法

动态规划和贪心算法的区别

如下：贪心法是每一步的最优解就是整体的最优解。0-1背包是属于动态规划，每一步的解不一定导致整体的最优解。对于你问“什么样的题用0-1背包问题作”就是需要你自己做题来体会了。如果全局的最优解可以用分布的最优解求出来，就用贪心，如果不是，就动态规划（0-1背包属于这类）。合并果子问题（可以自己去网上找哈~）就是典型的贪心，0-1背包问题就属于典型动态规划。贪心算法特性：贪心算法的关键不在于想到，而在于正确性的证明。要证明一个贪心算法是正确的，需要证明我们可以把一个最优解逐步转化为我们用贪心算法所得到的解。而解不会更差，从而证明贪心算法得到的解和最优解是一样好的（显然，最优解不可能更好)。而要证明一个贪心算法是错误的，只需要找到一个反例就可以了。动态规划和贪心算法都是一种递推算法，均有局部最优解来推导全局最优解，贪心算法：动态规划算法：贪心算法与动态规划。每次拿能拿的最大的，就是贪心。但是一定注意，贪心得到的并不是最优解，也就是说用贪心不一定是拿的最少的张数。

简述贪心，递归，动态规划，及分治算法之间的区别和联系

联系：都是问题求解之时的一种算法。区别：一、作用不同1、贪心算法：把子问题的解局部最优解合成原来解问题的一个解。2、递归算法：问题解法按递归算法实现。如Hanoi问题；数据的结构形式是按递归定义的。如二叉树、广义表等。3、动态规划：动态规划算法通常用于求解具有某种最优性质的问题。4、分治算法：可以再把它们分成几个更小的子问题，以此类推，直至可以直接求出解为止。二、方法不同1、贪心算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。2、递归算法：通过重复将问题分解为同类的子问题而解决问题。3、动态规划：将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。4、分治算法：将一个规模为N的问题分解为K个规模较小的子问题。三、特点不同1、贪心算法：根据题意选取一种量度标准。2、递归算法：递归就是在过程或函数里调用自身。3、动态规划：虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。4、分治算法：原问题可以分解为多个子问题；原问题在分解过程中，递归地求解子问题；在求解并得到各个子问题的解后。