第三章贪心算法

超过C的情况下让总价值最高。每一个物体可以只取走一部分，价值和
重量按比例计算。
7
-贪心算法
贪心算法的经典实例
• 思路点拨：本问题是在上一个问题的基础上增加了价值项，所以不能简
单地向上一题那样先选出轻的（轻的可能其价值也小），也不能先拿价
值大的（它可能特别重），而应该综合考虑两个因素。一种直观的贪心
可乘两个人。求用最少的船载所有人的方案。
8
-贪心算法
贪心算法的经典实例
• 思路点拨：考虑最轻的人i，他应该和谁一起乘呢？如果每个人都不能和
他一起乘，则只能每人乘一艘船。否则他应该选择能和他一起乘的人中
最重的一个人j。这样的选择只是让“眼前”的浪费最少，因此它是一种
贪心策略。
• 证明：
• 情况1：i不和任何一个人同乘一艘船，那么可以把j拉过来和他一起乘，总船数不会
法不从整体最优考虑，它所做出的选择只是局部最优解。
3
-贪心算法
贪心算法的概念及其特点
• 贪心算法是从问题的初始状态出发，通过若干次的贪心选择而得
到的最优值的一种求解问题的策略。
• 特点：
• 贪心选择：所谓贪心选择是指应用同一规则，将原问题变为一个相似的
但规模更小的子问题，而后的每一步都是当前看似最佳的选择，且这种
29
-贪心算法
贪心算法的经典应用-3
• 【输出格式】
• 对每组测试数据输出一个数字，表示要浇灌整块草坪所需喷头数
目的最小值。如果所有喷头都打开还不能浇灌整块草坪，则输出1。
• 【样例输入】
•3
• 8 20 2
•53
30
-贪心算法
贪心算法的经典应用-3
•
•
•

找硬币■假设有四种硬币，面值分别为现在要找给某顾客六角三分钱，哪种找钱方法拿出的硬币个数最少呢？八分的最大硬币，即又一个二角五分，如此一直做下去。

这种方法实际上就是贪心算法。

再找硬币■若硬币的面值改为一分、五分和一角一分3 种，而要找个顾客的是一角五分钱。

■还用贪心算法，将找个顾客1个一角一分的硬币和4个一分的硬币。

■然而，3个五分的硬币显然才是最好的找法。

贪心算法的特点■贪心算法总是作出在当前来看是最好的选择。

■就是说，贪心算法并不从整体最优上来考虑，所作出的选择只是某种意义上的局部最优选择。

■当然希望贪心算法得到的最终结果是最优的。

■可是贪心算法并不能保证最终结果是最优的。

■不过，在许多情况下，应用贪心算法能够得到整体最优解；并且在一些情况下，即使得到的不是最优解，也是一个很好的近似解。

贪心算法的一般框架■G reedy Algorithm(parameters) {■初始化；■重复执行以下的操作：■选择当前可以选择的(相容)最优解；■将所选择的当前解加入到问题的解中;■直至满足问题求解的结束条件。

■}最小生成树■设G = (V, E)是一个无向连通带权图，即一个网络。

E的每条边(v, w)的权为c[v][w]o■如果G的一个子图G是一棵包含G的所有顶点的树，则称G为G的生成树。

■生成树的各边的权的总和称为该生成树的耗费。

■在G的所有生成树中，耗费最小的生成树称为G 的最小(优)生成树。

树的基本性质.■连通无回路的图G称为树。

已■树是点比边多-的连通图，G连通且q二p-l。

■ ■树是点比边多一的无回路图：G无回路且q二p-1■树若添条边就有回路：G无回路，但对任意的u, veV(G),若uv纟玖G),贝ijG+uv中恰有一条回路■树若减条边就不连通：G连通，但对VeeE(G), G-e不连通。

■ n个顶点的连通图的生成树含有n-1条边。

最小生成树的贪心选择性质■令G中权最小的边为ei。

首先必定有图G的一棵最小生成树包含了■MM?■ Prim算法的做法：在保证连通的前提下依次选出权重较小的n-1条边（在实现中体现为n个顶点的选择）。

2019/10/15
8
当n不太大时，适当的取k值，此改进方法常常可以得到 最优解，但不能因此就说一般背包问题有多项式算法。 当n增大时，k不能随着n不断的加大，如k随n增大而同 时加大，其复杂性就是指数型而不是多项式型的了，而 如k取值较小，又不能保证得出最优解。
2019/10/15
9
例3．巡回推销员问题
此问题解的过程如下：
2019/10/15
11
d24(1)； d24(1)+d13(2)； d24(1)+d13(2)+d15(2)； d24(1)+d13(2)+d15(2)+d25(3)； d24(1)+d13(2)+d15(2)+d25(3)+[d45(6)]；
（下标中5出现了3次,顶点5有三条边相连,d45(6)放弃） d24(1)+d13(2)+d15(2)+d25(3)+[d35(9)]；
2019/10/15
5
例2. 背包问题
设有n=8个体积分别为54，45，43，29，23，21， 14，1的物体和一个容积为C=110的背包，问选择哪几个 物体装入背包可以使其装的最满。
如直接用贪婪算法，将物体由大到小顺次装入背包， 到装不下时再逐个试装更小的一些，直至试到最小的一 个或装满为止。按此处所给数据，先装入54和45两个， 容积尚余11，最后只能再装入体积为1的一个，总体积 达到100，并不算太满。此方法的好处是节省时间，主 要的运算时间是用来对n个元素进行排序，故其复杂性 是O（nlogn）。
d34=5 d23=5 d12=6 d35=6 d56=6
2019/10/15
25

贪心算法及几个常用的例题贪心算法：一、基本概念：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。

必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。

所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

二、贪心算法的基本思路：1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

三、贪心算法适用的问题贪心策略适用的前提是：局部最优策略能导致产生全局最优解。

实际上，贪心算法适用的情况很少。

一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。

四、贪心算法的实现框架从问题的某一初始解出发；while （能朝给定总目标前进一步）利用可行的决策，求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；五、贪心策略的选择因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。

几个经典的例子：一、定义什么是贪心算法呢？所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。

也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题都能产生整体最优解或整体最优解的近似解。

贪心算法的基本思路如下：1. .建立数学模型来描述问题。

2. 把求解的问题分成若干个子问题。

3. 对每个子问题求解，得到每个子问题的局部最优解。

4. 把每个子问题的局部最优解合成为原来问题的一个解。