贪心算法学习总结.pdf
版权申诉
171 浏览量
2022-05-26
15:52:10
上传
评论
收藏 524KB PDF 举报
----------------------------精品 word 文档 值得下载 值得拥有----------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------
----
贪心算法
一、算法思想
贪心法的基本思路:
—-从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一
步不能再继续前进时，算法停止.
该算法存在问题：
1. 不能保证求得的最后解是最佳的;
2. 不能用来求最大或最小解问题;
3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：
从问题的某一初始解出发；
while 能朝给定总目标前进一步 do
求出可行解的一个解元素;
由所有解元素组合成问题的一个可行解；
二、例题分析
1、[背包问题]有一个背包,背包容量是 M=150。有 7 个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品
重量 wi
价值 pi
分析：
目标函数： ∑pi 最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150）
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
(3）每次选取单位重量价值最大的物品，成为解本题的策略。 ？
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的 3 种贪心策略,都是无法成立（无法被证明）的，解释如下:
(1）贪心策略：选取价值最大者.反例:
W=30
物品：A B C
A
35
10
B
30
40
C
60
30
D
50
50
E
40
35
F
10
40
G
25
30
剩余12页未读，继续阅读
资源评论
