2.贪心方法的一般策略 问题的一般特征:问题的解是由n个输入的、满足某些事先给定的 条件的子集组成。 1)一般方法 根据题意,选取一种度量标准。然后按照这种度量标准对η个输入 排序,并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在 起不能产生一个可行解,则不把此输入加到这部分解中。否则,将当前 输入合并到部分解中从而得到包含当前输入的新的部分解 这一处理过程一直持续到n个输入都被考虑完毕,则记入最优解集 合中的输入子集构成这种量度意义下的问题的最优解 贪心方法:这种能够得到某种量度意义下的最优解的分级处理方法 称为贪心方法 注 贪心解亠最优解 直接将目标函数作为量度标准也不一定能够得到问题的最优解 使用贪心策略求解的关键是选取能够得到问题最优解的量度标准。2. 贪心方法的一般策略 问题的一般特征：问题的解是由n个输入的、满足某些事先给定的 条件的子集组成。 1）一般方法 根据题意，选取一种度量标准。然后按照这种度量标准对n个输入 排序，并按序一次输入一个量。 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一 起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前 输入合并到部分解中从而得到包含当前输入的新的部分解。 这一处理过程一直持续到n个输入都被考虑完毕，则记入最优解集 合中的输入子集构成这种量度意义下的问题的最优解 贪心方法: 这种能够得到某种量度意义下的最优解的分级处理方法 称为贪心方法 注： ➢ 贪心解 最优解 ➢ 直接将目标函数作为量度标准也不一定能够得到问题的最优解 ➢ 使用贪心策略求解的关键是选取能够得到问题最优解的量度标准。 ？ ＝