贪心法和动态规划算法的比较分析

❶ 动态规划和贪心法有什么区别有什么联系

动态规划和贪心算法都是一种递推算法
均有局部最优解来推导全局最优解

不同点：
贪心算法：
1.贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留。
2.由（1）中的介绍，可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。

动态规划算法：
1.全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解
2.动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解
3.边界条件：即最简单的，可以直接得出的局部最优解

注：给我你电子邮箱，我把详细资料发过去

❷ 贪心算法——活动安排问题

•贪心算法的特点是每个阶段所作的选择都是局部最优的，它期望通过所作的局部最优选择产生出一个全局最优解。

贪心与动态规划： 与动态规划不同的是，贪心是 鼠目寸光 ；动态规划是 统揽全局 。

–动态规划：每个阶段产生的都是全局最优解

•第i阶段的“全局”： 问题空间为(a1, … , ai)

•第i阶段的“全局最优解”：问题空间为 (a1, … , ai)时的最优解

–贪心：每个阶段产生的都是局部最优解

•第i阶段的“局部”：问题空间为按照贪心策略中的优先级排好序的第i个输入ai

•第i阶段的“局部最优解”： ai

•贪心选择性质：所求问题的全局最优解可以通过一系列局部最优的选择（即贪心选择）来达到。

–这是贪心算法与动态规划算法的主要区别。

•最优子结构性质：当原问题的最优解包含子问题的最优解时，称此问题具有最优子结构性质。

最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征

•要求高效地安排一系列争用某一公共资源（例如会议室）的活动（使尽可能多的活动能兼容使用公共资源）。

–设有n个活动的集合E={e1,e2…en}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。

–若区间[si,fi)与区间[sj,fj)不相交，则称ei和ej是相容的。也就是说，当si≥fj或sj≥fi时，活动i和活动j相容。

•活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

❸ 大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系

对于，大学课程《算法分析与设计》中动态规划和贪心算法的区别和联系这个问题，首先要来聊聊他们的联系：1、都是一种推导算法；2、将它们分解为子问题求解，它们都需要有最优子结构。这两个特征师门的联系。

拓展资料：

贪婪算法是指在解决问题时，它总是在当前做出最佳选择。也就是说，在不考虑全局优化的情况下，该算法在某种意义上获得了局部最优解。贪婪算法不能得到所有问题的全局最优解。关键是贪婪策略的选择。

动态规划是运筹学的一个分支，是解决决策过程优化的过程。20世纪50年代初，美国数学家R·贝尔曼等人在研究多阶段决策过程的最优化问题时，提出了着名的最优化原理，建立了动态规划。动态规划在工程技术、经济、工业生产、军事和自动控制等领域有着广泛的应用，在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题上都取得了显着的成果。

❹ 分析用动态规划和贪心算法求解背包问题的差异

动态规划本质是以空间换时间，算出了所有可行解的值域。

而贪心算法，每次选则最优的，而结果未必最优。
举个简单例子。
背包能装8kg,有3个物品，分别为3kg,4kg,5kg
动态规划，是计算，3+4， 3+5，得出解，最大的是3+5=8kg
贪心算法，是选择，第一次选最大的：5kg<8kg，第二次选则剩下的最大的4kg，4+5>8,故而解为5kg。