第7章-贪心法

1、第7章，贪婪方法，1，2，3，4，概述，图形问题中的贪婪方法，组合问题中的贪婪方法，总结，假设有几种货币的面值分别为3元，1元，8美分，5美分和1美分，有必要给客户4元6美分的现金。为了尽量减少支付的金额，需要三种货币：一个3元和两个8美分。根据贪婪的方法，顾客被发现有四种货币：一个3元，一个1元，一个50美分和一个10美分。什么样的包装方式会使背包旅行项目的总收入最大化？背包问题，贪心法是一种简单有效的方法。它只根据目前已有的信息来选择解决问题的策略，一旦做出选择，无论将来的结果如何，它都不会改变。贪心法的设计思想，贪心法不是从全局最优来考虑的，但它所做的选择在某种意义上只是局部最优。这种局

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=(A

3、E)B)/(BE)，真分数(AE) B)/BE可以通过从真分数中减去最大埃及分数而得到，其中，埃及得分想法，问题描述：TSP问题意味着旅行者想去N个城市旅行，要求每个城市只经历一次，然后返回出发城市，并要求最短的距离。图问题中的贪婪TSP问题从任何一个城市开始，并从从未去过的城市中选择最近的一个，直到它经过所有的城市并最终返回到起始城市。想法1:最近邻策略，解决方案流程？每次，在整个图中选择最短的边，并将其添加到解集。然而，有必要确保添加到解集的边最终形成哈密尔顿环。因此，当从剩余边集e中选择一条边(u，v)加入解集s时，应满足以下条件：边(u，v)是边集e中代价最小的边；将边(u，v)添加到

4、解集s后，s中不会生成循环；在边(u，v)被添加到解集合s之后，在s中不产生分支，想法2:最短链接策略，解过程？给定无向连通图G=(V，E)，求图G的最小色数K，这样G中的顶点可以用K种颜色着色，并且任何两个相邻的顶点可以不同地着色。图问题中的贪婪正规图着色问题，考虑顶点阶1，5，2，3，4得到近似解，考虑顶点阶1，2，3，4，5得到最优解，图问题中的贪婪正规图着色问题，1。所有顶点都处于未暴露状态；2颜色k初始化为0；3.循环，直到所有顶点都着色。3.1下一个颜色k；3.2依次调查所有顶点3.2.1如果顶点1是彩色的，转到步骤3.2；3.2.2如果顶点I的颜色k不冲突，则颜色I=k；4.输出

5、每个顶点的颜色；描述：colorn表示顶点n的着色。图问题中的贪婪图着色问题，组合问题中的贪婪背包问题，问题描述：给定n个项目和一个容量为c的背包，项目I的权重为wi，其值为vi，背包问题是如何选择装载在背包中的项目，以使装载在背包中的项目的总值最大化。背包问题和0/1背包问题有什么区别？贪婪策略的选择：(1)选择价值最大的项目；(2)选择最轻的项目；(3)选择单位重量最大值的项目。哪个更合理？如何处理它？50公斤，策略1:选择最有价值的物品；策略2:选择最轻的物品；策略3:选择单位重量价值最大的物品。1.改变阵列w和v的排列顺序，使它们根据单位重量值vi/wi按降序排列；2.将数组xn初始化为0；3.I=1；4.循环至(wiC) 4.1将第三个项目放入背包：Xi=1；4.2摄氏度=零摄氏度；4.3 I；5.Xi=成本/收益；背包问题算法，让背包容量为c，有n个项目，项目的重量存储在数组wn中，值存储在数组vn中，问题的解存储在数组xn中。组合问题中的贪婪活