贪心算法 入门.

Presentation on theme: "贪心算法 入门."— Presentation transcript:

1 贪心算法 入门

2 本节将介绍以下内容： 贪心算法的基本思想 贪心算法的基本思路 贪心算法的进行过程 基本题型与例题解析

3 贪心算法的基本思想 在不可预见后面会发生什么的情况下，我们都会选择在当前情况 下看起来是最好的选择。这就是贪心算法的基本思想。
那么贪心算法对于整体来说，不一定作出了最好的决策，只是在 一定意义上是局部最优解。不过对许多问题，它作出的局部最优 解的组合就是整体最优解。最小生成树的Prim算法和Kruskal算 法就是贪心算法的经典应用。 在某些情况下，我们并不需要最优解，只是需要一个较优解，那 么贪心算法执行简单，是很好的选择，在现实中应用广泛。

4 贪心算法的基本要素 一个问题可以贪心，需要有以下两个性质：
贪心选择性：这个问题的整体最优解可以通过一系列局部最优的 选择来达到。在后面有动态规划的内容，贪心与动态规划都是寻 找最优解的手段，但是动态规划是从后往前寻找答案，而贪心是 从前往后寻找答案，所以贪心相比动态规划有一定的局限性，但 由于构造简单，仍是一个重要的算法。 最优子结构性质：这个问题的最优解包含其子问题的最优解时， 这个问题就有最优子结构性质。如果一个问题不拥有最优子结构 性质，就不能用贪心与动态规划解决。

5 贪心算法的基本思路 从问题的初始状态开始，往最终状态前进，每次都选择当前最好 的选择。当到达最终状态时停止；如果不能再作出选择，又未到 达最终状态，那么这个问题不能或利用贪心思想不能到达最终状 态，停止。 存在的问题： 1.不能保证最后的解是最优解。 2.不能用来求最大或最小解问题。 3.只能求满足某些约束条件的可行解范围。

6 贪心算法的执行过程 有一个背包，其容量M一定。物品有若干个，要求尽可能让装入 背包中的物品的总价值最大，但是不能超过总容量。
思路1：每次挑选价值最大的物品，直到无法选择物品。 思路2：每次挑选重量最小的物品，直到无法选择物品。 思路3：每次选择单位重量价值最大的物品，直到无法选择物品。 无法选择物品两种情况。

7 思路1：选取价值最大 M=30 选择结果为A。 但是，更优的结果是选择B和C。说明思路1是不可行的。 物品ID A B C 物品重量 28
12 物品价值 30 20

8 思路2：选取重量最小 M=30 选择的结果为A和C。 但是，最优的结果是选择B，说明思路2也是不可行的。 物品ID A B C 物品重量
10 30 12 物品价值 15

9 思路3：选取单位重量价值最大 W=30 不加优化的情况下，选择是A。 但是，最优的选择是B和C。说明思路3也是不可行的。 物品ID A B
物品重量 28 20 10 物品价值

10 思路3：选择单位重量价值最大 加上一点优化，当单位重量价值相同的时候，先选择重量最小的。 这样对于上一组数据的选择是B和C，正确。 W=30
选择为B和C，但显然选择A更优，说明优化后的思路3还是错误的。 物品ID A B C 物品重量 30 15 10 物品价值

11 背包问题的解决 从上面的三种思路来看，该背包问题并不能用贪心解决。
一般来说，背包问题用贪心解决不能保证得到的是整体最优解， 所以背包问题需要用动态规划来解决。 但是经过这样三种思路的分析，应该对贪心的步骤有了一定的理 解。下面来解决一下贪心能够解决的问题。 是不是很失望？哈哈哈哈哈

12 种类一：一般贪心(交换)问题 HDU 1009 Fat Mouse’ Trade
Fat Mouse 准备了M磅猫粮，准备和看守存放了他最喜欢的食物 -咖啡豆的房间的猫进行交易。猫看守着N间房间，第i间房间存放 了J[i]磅咖啡豆，交换所有咖啡豆需要F[i]磅的猫粮，FM不必交换 整个房间的咖啡豆，也就是说，他可以用(F[i]*a)%磅的猫粮交换 得到(J[i]*a)%磅咖啡豆。现在他请你帮忙，帮他交换到最多数量 的咖啡豆。

13 HDU 1009 Fat Mouse’ Trade Input： Output：
Output： 猫粮数 房间数 第一组数据，保留3位小数 咖啡豆数 猫粮数 猫粮数 房间数 第二组数据，保留3位小数 咖啡豆数 猫粮数 -1 -1 结束 结束，不进行处理

14 HDU 1009 Fat Mouse’ Trade 分析：
题目描述和之前的背包问题很像，但是题目多了一个可以用一部 分猫粮换取一部分咖啡豆的条件。如果那个背包问题也加入这样 的条件，那就可以保证背包能够装满，这样就可以用贪心去解决。 那么这个问题，可以选择之前的思路三，选择每单位猫粮换取的 咖啡豆最多的房间进行交易，直到猫粮用完。 得出解决方案后，先验证一下第一组数据，三个房间分别是 3.5；1.333；2.5，先换房间1和3的，都可以全部换到。剩下房间 2不能换到所有的咖啡豆，因为猫粮剩余1，只能换到1/3，那么 结果就是7+5+4*(1/3)=13.333，答案正确。 题解

15 类型二：时间安排问题(区间覆盖) HDU 2037 今年暑假不AC

16 HDU 2037 今年暑假不AC Output： 5 能完整地看5个节目 Input：
电视节目数量 某个节目开始时间和结束时间 输入0结束 Output： 能完整地看5个节目

17 HDU 2037 今年暑假不AC 分析： 时间安排问题，用贪心总能得到整体最优解，用数学归纳法可以 证明，可以自己尝试证明，从略。
可以先对所有的节目以结束时间从早到晚进行排序，结束时间相 同的时候，按照开始时间从早到晚排序。 然后看第一个节目，它的开始时间最早，结束时间最早，那么这 个节目是一定要看的。然后后面的节目都对比前一个看的节目的 结束时间，如果此时还在看上一个节目，那么继续看前一个节目， 放弃这一个节目。直到分析完所有节目。 题解

18 类型二：时间安排问题(区间覆盖) 这种题目还有一种变形，都是区间覆盖问题。
在一维空间，有一些线段，这些线段有可能会有重叠，要求去掉 其中一些线段，使得线段不重叠而且覆盖长度最长。 这个问题其实就是时间安排问题，但是如果没有遇见过，基本不 会想到用贪心可以解决。 如果这个问题不要求去掉线段，而是直接求总覆盖长度，就变成 了类型三：线段覆盖问题，实质上仍是区间覆盖问题。

19 类型三：线段覆盖问题(区间覆盖) I 1 2 3 4 5 6 7 8 9 10 s[i] 11 f[i] 12 13 15 这种类型和类型二非常类似，只需要稍加修改，排序的时候先按 照开始时间排序，再按结束时间排序。总长先记为线段1的全长， 然后线段2和线段1比较，如果线段2不与线段1重复，总长就加上 线段2的全长；如果线段2结束点在线段1结束点前，那么线段2长 度不计；如果线段2与1重复且结束点不在线段1内部，则总长加 上线段1结束点到线段2结束点的长度。 10 2 3 3 5 4 7 5 6 6 9 7 8 8 12 9 10 10 13 11 15 题解

20 类型四：数字组合问题 这种类型可以归类到类型一中，不过类型一说是交易类型，所以 这种就单独成一类好了。
这种题目可以简单，也可以难，难题一般是思路不好想。 例1：给出一些整数，要求对这些数字的各数位重新排序并组合， 使组成的数字最大。 解：题目说的是对数字的数位排序，那么肯定是把0-9所有数字个 数统计一下，按照9 8 7…0的顺序输出即可。

21 类型四：数字组合问题 Input： 5 5438 4452 21 402 248 0 Output： 8855444443222210
Output： 数字个数 结束

22 类型四：数字组合问题 例2：HDU 5718 Oracle
题目给出一个不含前导零的正整数，要求将这个整数拆分成两个 不含前导零的正整数，使这两个数的和最大。如果不存在这样的 方案，输出Uncertain。 Input： Output： Uncertain Hint： 第一组拆分成21和1 第二组拆分成33和2 第三组无法拆分 数据组数

23 HDU 5718 Oracle 分析： 不能拆分的情况，有两种，1是只有一位，2是去掉0后只有一位， 在判断的时候这两种可以归为一种。例：1和10000。 能拆分的情况，一定是拆分成n-1位和1位的两个数，这个1位的 数，一定取除了0以外的最小的数。n-1位的数就像例1一样，从 大到小排好。题目要求输出和，进行一下大数加法就可以了。 题解

24 return 0; 如对知识点有问题可以联系： QQ： 如对题目或题解有问题除了上面的联系方式， 也可以在题解页面评论进行评论。 15软件工程 李天阳