贪心算法应用研究

《贪心算法应用研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、目录1、贪习算法的基本概念2、贪习算法总论2.1贪习算法的特点2.2该算法存在问题2.3贪心算法解题的运用范围：2.4贪心算法解题的一般思路：2.4.1采用贪心算法的条件2.4.2处理流程3、贪心算法经典应用举倒3.1找零钱问题4、贪心算法与动态规划算法的比餃4.1用贪婪法解0/1背包问题4.1.1算法分析4.1.2程序实现4.2用动态规划法解0/1背包问题4.2.1什么是运态规划算法4.2.2最优了序列性质4.2.3最优原则4.2.4动态规划递划方程4.2.5算法复朵度4.2.6程序实现4.3结论5、总结参考文献贪心算法应用研究陈峰洋（湖北仙桃职业学院，计算机网络0508班103

2、050844）摘要：本文对贪心算法进行了研究，通过对贪心算法经典例题的分析阐述了贪心算法的运用范围及解题步骤，以0/1苗包问题为例，-9动态规划算法进行了比较.关键词：贪心算法：0/1背包问题：VC1.贪心算法的基本概念在弄清什么是贪心算法Z前，我们首先來看看什么叫算法。“算法”一词最早來自公元9世纪波斯数学家比阿勒•霍瓦里松的一本影响深远的著作《代数对话录》。20世纪的英国数学家图灵提出了著名的图灵论点，并抽象出了一台机器,这台机器被我们称之为图灵机。图灵的思想对算法的发展起到了重要的作用。算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说，就是计算机解题的过程。

3、在这个过程中，无论是形成解题思路还是编写程序，都是在实施某种算法。前者是推理实现的算法，后者是操作实现的算法。一、算法的特征输入：一个算法必须有零个或多个输入量。输出：一个算法应有一个或多个输出量，输出量是算法计算的结果。确定性：算法的描述必须无歧义，以保证算法的执行结果是确定的。有穷性：算法必须在有限步骤内实现。注：此处“有限”不同丁数学概念的“有限”，天文数字般的有限对于实际问题并无意义。有效性：乂称可行性。能够实现，算法中描述的操作都是可以通过己经实现的基本运算执行有限次來实现。二、在设计算法时，通常应考虑以下原则1）正确性A.程序不含语法错谋：B.程序对几组输入数据能够得出

4、满足规格耍求的结果：C.程序对精心选择的、典型的、苛刻的、带有刁难性的儿组输入数据能够得出满足规格要求的结果：D.程序对一切合法的输入数据都能产牛满足规格耍求的结果。2）可读性算法的第一目的是为T阅读和交流：可读性有助丁对算法的理解；可读性有助于对算法的调试和修改。3）高效率与低存储量处理速度怏：存储容量小算法常常含有重复的步骤平和一些比较或逻辑判断。如杲一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间、空间或效率來完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度來衡最。时间和空间是矛盾的、实际问题的求解往往是求得时间和空间的

5、统一、折中。三、什么是贪心算法我们来看一个找硬币的例子。假设有四种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的换币和3个一分的换币交给顾客。这种找硬币方法与其他的找法相比，所拿出的换币个数是最少的。这里，我们下意识地使用了这样的找换帀算法：首先选出一个血值不超过六角三分的最大硬币，即二角五分：然后从六角三分中减去二角五分，〜1T—角八分;再选出一个面值不超过三角八分的最大硬币，即乂一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。顾名思义，贪心算法总是作出在当前看来是最好的选择

6、。也就是说贪心算法并不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，我们希與贪心算法得到的最终结果也是整体最优的。上面所说的找陨币算法得到的结杲就是一个整体最优解。找硬币问题木身具有最优子结构性质，它可以用动态规划算法来解。但我们看到，用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的一些特性。例如，上述找硬币的算法利用了硬币而值的特殊性。如果硬币的而值改为-•分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，我们将找给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好的找法。虽然贪心算法不是对所有问题都能得到整

7、体最优解，但对范1弔1相当广的许多问题它能产生整体最优解。如图的单源最短路径问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解。2、贪心算法总论首先，总结一下什么是贪心：本人认为，所谓贪心算法，就是对于一个初始状态，经过多次转化转化为某个状态，每一次转化都遵循一个特定的函数(即：贪心策略)，保证整个过程最终结果和每一步都是某方面的最优解。2.1贪心算法的特点根据以上一句理解，贪心算法有这样儿个特点，并与其他算法有