文档介绍：一、算法思想贪心法的基本思路:——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。该算法存在问题:;;。实现该算法的过程:从问题的某一初始解出发;while能朝给定总目标前进一步do 求出可行解的一个解元素;由所有解元素组合成问题的一个可行解;二、例题分析1、[背包问题]有一个背包,背包容量是M=150。有7个物品,物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大,但不能超过总容量。物品A  B  CDEFG重量35  30  60  50  40  10  25  价值  10  40  3050  35  40  30分析:目标函数:∑pi最大约束条件是装入的物品总重量不超过背包容量:∑wi<=M(M=150)(1)根据贪心的策略,每次挑选价值最大的物品装入背包,得到的结果是否最优?(2)每次挑选所占空间最小的物品装入是否能得到最优解?(3)每次选取单位容量价值最大的物品,成为解本题的策略?虽然设计一个好的求解算法更像是一门艺术,而不像是技术,但仍然存在一些行之有效的能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。一般情况下,为了获得较好的性能,必须对算法进行细致的调整。但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。   本章首先引入最优化的概念,然后介绍一种直观的问题求解方法:贪婪算法。最后,应用该算法给出货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树等问题的求解方案。   本章及后续章节中的许多例子都是最优化问题(optimizationproblem),每个最优化问题都包含一组限制条件(constraint)和一个优化函数(optimizationfunction),符合限制条件的问题求解方案称为可行解(feasiblesolution),使优化函数取得最佳值的可行解称为最优解(optimalsolution)。   例1-1[渴婴问题]有一个非常渴的、聪明的小婴儿,她可能得到的东西包括一杯水、一桶牛奶、多罐不同种类的果汁、许多不同的装在瓶子或罐子中的苏打水,即婴儿可得到n种不同的饮料。根据以前关于这n种饮料的不同体验,此婴儿知道这其中某些饮料更合自己的胃口,因此,婴儿采取如下方法为每一种饮料赋予一个满意度值:饮用1盎司第i种饮料,对它作出相对评价,将一个数值si作为满意度赋予第i种饮料。   通常,这个婴儿都会尽量饮用具有最大满意度值的饮料来最大限度地满足她解渴的需要,但是不幸的是:具有最大满意度值的饮料有时并没有足够的量来满足此婴儿解渴的需要。设ai是第i种饮料的总量(以盎司为单位),而此婴儿需要t盎司的饮料来解渴,那么,需要饮用n种不同的饮料各多少量才能满足婴儿解渴的需求呢?   设各种饮料的满意度已知。令xi为婴儿将要饮用的第i种饮料的量,则需要解决的问题是:   找到一组实数xi(1≤i≤n),使n?i=1sixi最大,并满足:n?i=1xi=t及0≤xi≤ai。   需要指出的是:如果n?i=1ai<t