贪心算法的应用贪心法的应用.doc

贪心算法的应用 课程名称： 算法设计与分析 院 系： 计算机科学与信息工程学院 学生姓名： **** 学 号： ********** 专业班级：********************************** 指导教师： ****** 201312-27 贪心算法的应用 摘 要：顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法求问题一般具有两个重要性质：贪心选择性质和最优子结构性质。所谓贪心选择性是指所求问题的整体最优解可以通过一系列局部最优解的选择，即贪心选择达 到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法主要区别。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。 背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用贪心法解决这个问题。 关键词：贪心法 背包问题 最优化 目 录 第1章 绪论 3 1.1 贪心算法的背景知识 3 1.2 贪心算法的前景意义 3 第2章 贪心算法的理论知识 4 2.1 问题的模式 4 2.2 贪心算法的一般性描述 4 第3章 背包问题 5 3.1 问题描述 5 3.2 问题分析 5 3.3算法设计 5 3.4 测试结果与分析 10 第4章 结论 12 参考文献 13 附件 13 第1章 绪论 1.1 贪心算法的背景知识 贪心算法又叫登山法，它的根本思想是逐步到达山顶，即逐步得最优解，是解决最优化问题时的一种简单但适用范围有限的策略。“贪心”可以理解为以逐步的局部最优，达到最终的全局最优。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。一定要注意，选择的贪心策略要有无后向性，即某阶段状态一旦确定以后，不受这个状态以后的决策影响。也就是说某状态以后的过程不会影响以前的状态，至于当前的状态有关，也称这种特性为无后效性。已经学会在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。例如为了使生产某一产品所花费的时间最少，一种贪心的策略就是在生产该产品的每一道工序上都选择最省时的方法。所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。 1.2 贪心算法的前景意义 贪心算法的主要思想是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时算法停止。该算法存在问题其一是不能保证求得的最后解是最佳的；其二，不能用来求最大或最小解问题；其三，只能求满足某些约束条件的可行解的范围。所以贪心算法是解决最优化问题时的一种简单但适用范围有限的策略。贪心算法无后向性在解的范围可以确定的情况下，可以采用枚举或递归策略，找出所有的结果，一一比较它们，可能在有限的时间内找不到问题的解。这时可以考虑用贪心的策略，选取那些最可能到达解的情况来考虑。贪婪算法策略在《数据结构》课程中的算法也有广泛的应用，如霍夫曼树、构造最小生成树的Prim算法和Kruskal算法的决策过程，都是使用的贪婪算法策略。 第2章 贪心算法的理论知识 2.1 问题的模式 对于背包问题。 重量为w1,w2,w3…wn的若干物品和容量为m的背包，物品的价值分别为p1,p2,p3…pn。要求找出这n个物品的一个子集，使其尽可能是选