贪心法.ppt

详细的算法设计PPT,非常适合刚入门的人学习,快来下载吧

贪心法 贪心法 补充内容 算法

介绍了利用贪心法解决0-1背包问题、通信网络问题、机器调度、最短路径等算法的思想，是学习贪心解决策略的入门和提高的有效资源。

一 0 1背包问题的算法设计策略分析 1 算法复杂性分析的方法介绍 算法复杂性是算法运行所需要的计算机资源的量 需要时间资源的量称为时间复杂性 需要的空间资源的量称为空间复杂性 这个量应该只依赖于算法

可行解的确定 定理3.3: 设J是k个作业的集合=i1,i2,ik是J中作业的一种排列它使得di1di2dikJ是一个可行解当且仅当J中的作业可以按照的次序而又不违反任何一个期限的情况来处理 定理3.

重量最轻的物品优先的贪心策略。 价值最大的物品优先的贪心策略。 单位价值最大的物品优先的贪心策略。 随机选择物品的贪心策略

有1元、5元、10元、50元、100元、500元的硬币各c1、c5、c10、c50、c100、c500枚。 现在要用这些硬币来支付A元,最少需要多少枚硬币? 假定本题至少存在一种支付方案 附加条件0

算法设计中有关贪心法的几个实用小程序，包括背包问题，带期限的作业排序，高精度数，调度问题。仅供学习之用，欢迎交流！

Greedy Law Seminar

题目描述：TSP（TravelingSalesmanProblem）是指：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。TSP的历史很久，最早的描述是1759年