1、第七章 贪心法1234概述图问题中的贪心法组合问题中的贪心法小结假设有面值为 3元、 1元、 8角、 5角、 1角的货币若干枚，需要找给顾客 4元 6角现金，为使付出的货币的数量最少，需要 3张货币： 1个 3元和 2个 8角。 而按贪心法找给顾客的是 1个 3元、 1个 1元、 1个 5角和 1个 1角共 4张货币。找零钱问题采用怎样的装包方法才会使装入背包物品的总收益最大？背包问题贪心法是一种简单有效的方法。它在解决问题的策略上只根据当前已有的信息就做出选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。贪心法的设计思想贪心法并不是从整体最优考虑，它所做出的选择只是在某种意义
2、上的局部最优。这种局部最优选择并不总能获得整体 最优解，但通常能获得 近似最优解 。如果一个问题的最优解只能用蛮力法穷举得到，则贪心法不失为寻找问题近似最优解的一个较好办法。贪心法的设计思想一个简单的例子 埃及分数问题描述：古埃及人只用分子为 1的分数，在表示一个真分数时，将其分解为若干个埃及分数之和，例如： 7/8表示为 1/2 + 1/3 + 1/24。埃及分数问题要求把一个真分数表示为最少的埃及分数之和的形式。设真分数为 A/B， B除以 A的整数部分为 C，余数为 D，则有下式成立：B = A C + D即：B/A = C + D/A 1/(C + 1)即 1/(C + 1) 即为真分数 A/B包含的最大埃及分数。设 E = C + 1，由于A/B 1/E = (AE) B)/(BE)则真分数减去最大埃及分数后，得到真分数(AE) B)/BE该真分数可能存在公因子，需要化简。 埃及分数 想法问题描述： TSP问题是指旅行家要旅行 n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。图问题中的贪心法 TSP 问题 从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。想法 1：最近邻点策略C= 3 3 2 63 7 3 23 7 2 52 3 2 36 2 5 3 求解过程？
