贪心算法

文章作者 100test 发表时间 2011:03:18 20:32:10
来源 100Test.Com百考试题网

　　所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

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

　　贪心算法的基本思路如下：

　　1.建立数学模型来描述问题。

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

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

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

　　实现该算法的过程：

　　从问题的某一初始解出发；

　　while 能朝给定总目标前进一步 do

　　求出可行解的一个解元素；

　　由所有解元素组合成问题的一个可行解；

　　下面是一个可以试用贪心算法解的题目，贪心解的确不错，可惜不是最优解。

　　例题分析

　　[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。

　　要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。

　　物品 A B C D E F G

　　重量 35 30 60 50 40 10 25

　　价值 10 40 30 50 35 40 30

　　分析：

　　目标函数： ∑pi最大