贪心算法之初见ppt课件.ppt

贪心算法,武松打老虎,问题描述：曾经因打虎而闻名的武松在x年后接到了景阳冈动物园的求助信，信上说：最近我们动物园逃跑了几只老虎，请您把它们抓回来，thank you！武松接到信后立刻上了山。正当他到半山腰是，suddenly！跳出n只猛虎来。每只老虎都有一块虎牌，牌上写着的是每一只虎最大拥有的体力，当武松与老虎PK时，若老虎的体力先用完，那么老虎over，否则武松over。求武松在over之前最多能干掉几只老虎？（注：老虎是一只只上的）输入文件：第一行两个数字n(n50000),t0(武松的体力)。第二行n个数字，分别代表每只老虎的体力。所有变量都不超过long int范围。输出文件：一行，最多能干掉的老虎数。样例输入：6 10 1 5 3 2 4 6样例输出：4,分析,题目所求：最多能干掉的老虎数目已知武松体力，每只老虎的体力，每干掉一只老虎，都会消耗相应体力。为了干掉更多的老虎,每次干掉体力最少的老虎,老虎体力：,排序后体力：,武松体力,10,第一轮PK：10-1=9,第二轮PK：9-2=7,第三轮PK：7-3=4,第四轮PK：4-4=0,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,当前看来是最好的选择:,打死体力最少的老虎！,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,武松体力：,10,打死老虎数目：,0,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,武松体力：,9,打死老虎数目：,1,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,武松体力：,7,打死老虎数目：,2,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,武松体力：,4,打死老虎数目：,3,贪心算法（贪心策略）：每次都作出在当前看来是最好的选择，不断循环，直到获得问题的完整解。,老虎体力：,武松体力：,0,打死老虎数目：,4,武松的体力已经不能打死任何一头老虎了，已得到问题的完整解。,贪心算法一定能得到最优解吗？,要满足以下条件：,1、最优子结构；2、贪心选择性质；,最优子结构性质(最优化原理),定义：当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。,例如图2中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。,(最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。),接下来证明刚才的问题是否具有最优子结构性质,最优子结构性质(最优化原理),定义：当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。,每打死一只老虎的体力值为ai，要使打死的老虎总数最多，就要使武松剩下的体力t0-ai能打死更多的老虎。即一个与武松体力t0相关的问题，可以转换为t0-ai体力相关的问题。体力为t0-ai的是体力为t0的子问题。体力是t0时的最优解，包括了体力为t0-ai的最优解。该问题具备最优子结构。,最优子结构性质(最优化原理),定义：当问题的最优解包括了其子问题的最优解时，称该问题具有最优子结构性质。,当武松体力值为t0时,打死一只体力值为ai的老虎,当武松体力值为t0-ai 时,子问题,最优解A方案,最优解B方案,此时的最优解,此时的最优解,包含于,若B不包含于A，那么当武松的体力值为t0-ai时，其最优解必定不是B。矛盾。所以，B一定是A的子集。,举个栗子,老虎体力：,武松体力,10,最优解为：,打死体力为：1，2，3，4的老虎,当打死一只体力为1的老虎后。,老虎体力：,武松体力,9,最优解为：,打死体力为：2，3，4的老虎,子集,贪心选择性质,定义：所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来达到。,贪心选择：每次选择剩下的老虎中体力最少的。武松剩下的体力值越大，能打死的老虎就越多。使用贪心选择（每次选择剩下的老虎中体力最少的），能使武松剩下的体力最大。这种贪心选择，能保证全局最优，即能保证打死最多数量的老虎。因此具备贪心选择性质。,贪心选择性质：所求问题的整体最优解可以通过一些列局部最优的选择，即贪心选择来达到。,确定贪心选择方法,非常重要！,武松打老虎的贪心选择为：,每次选择剩下的老虎中体力最少的。,当前看来是最好的选择,最大数,题目描述：设有n个正整数（n20），将它们联接成一排，组成一个最大的多位整数。输入描述：第一行一个正整数n。第二行n个正整数，空格隔开。输出描述：连接成的多位数样例输入：Sample 1:313 312 343样例输出：Sample 1:34331213,分析,贪心选择方法,方案一：,把整数按从大到小的顺序排列起来,13 312 343,343 312 13,反例：7 23 4 246贪心选择答案：2462374正确答案：7424623,方案二：,先按每个整数的第一位数字排序，大小相同的再按第二位数字排序，以此类推,7 23 4 246,7 4 246 23,反例：12 121贪心选择答案：12112正确答案：12121,四个数字第一位分别是7、2、4、2；排列好2个数字（7和4）两个2开头的数比较下一位：3、4246在23之前,分析,完美方案：,先把整数化成字符串，然后再比较a+b和b+a，如果a+bb+a，就把a排在b的前面，反之则把a排在b的后面。,如：12 123,因为：1212312312,所以：123在12之前,如：12 121,因为：1211212121,所以：12在121之前,代码框架,int cmp(char *s1,char *s2) 比较函数 int main()scanf(%d,i+) 读取n个数 将n个数使用cmp()函数排序按排好的顺序输出（中间无空格）,线段覆盖,题目描述：在一个数轴上有n条线段，现要选取其中k条线段使得这k条线段两两没有重合部分（端点可以重合），问最大的k为多少输入描述：输入文件的第1行为一个正整数n，下面n行每行2个数字ai，bi，描述每条线段。输出描述：输出文件仅包括1个整数，为k的最大值样例输入：30 22 41 3样例输出：2,分析,贪心选择方案：,每次选取线段右端点坐标最小的线段，保留这条线段，并把和这条线段有公共部分的所有线段删除。重复这个过程，直到任两条线段之间都没有公共部分。,因为右端点坐标最小，可以保证所有与这条线段没有公共部分的线段都在这条线段的右边，且所有与这条线段有公共部分的线段两两之间都有公共部分。 又根据题意，在这些有公共部分的线段中，最后只能保留一条。显然，右端点坐标最小，对后面线段的影响最小，所以，应保留这条线段。,那么，如何证明以上贪心策略的正确性呢,？,每次取左端点坐标最小的行不行？,每次取长度最短行不行？,均分纸牌,题目描述 有 N 堆纸牌，编号分别为 1，2，, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若干张纸牌，然后移动。移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。例如 N=4，4 堆纸牌数分别为：98176移动3次可达到目的：从 取 4 张牌放到 （9 8 13 10） - 从 取 3 张牌放到 （9 11 10 10）- 从 取 1 张牌放到（10 10 10 10）。输入描述： 第一行N（N 堆纸牌，1 = N = 100） 第二行A1 A2 An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000）输出描述：输出至屏幕。格式为：所有堆均达到相等时的最少移动次数。样例输入49 8 17 6样例输出：3,分析,设ai为第i堆纸牌的张数（0=i=n），v为均分后每堆纸牌的张数，s为最小移到次数。,按照从左到右的顺序移动纸牌。如第i堆(0v，则将ai-v张纸牌从第I堆移动到第I+1堆；（2） 若aiv，则将v -ai张纸牌从第I+1堆移动到第I堆；为了设计的方便，我们把这两种情况统一看作是将aI-v张牌从第I堆移动到第I+1堆；移动后有：aI:=v；aI+1:=aI+1+aI-v；,贪心选择：,分析,我们继续按规则分析移牌过程，从第二堆移出9张到第一堆后，第一堆有10张纸牌，第二堆剩下-7张纸牌，再从第三堆移动17张到第二堆，刚好三堆纸牌数都是10，最后结果是对的，从第二堆移出的牌都可以从第三堆得到。我们在移动过程中，只是改变了移动的顺序，而移动的次数不变，因此此题使用贪心法是可行的。,在从第i+1堆中取出纸牌补充第i堆的过程中，可能会出现第i+1堆的纸牌数小于零(ai+1+ai-v0 )的情况。如n=3，三堆纸牌数为（1，2，27）这时v=10，为了使第一堆数为10，要从第二堆移9张纸牌到第一堆，而第二堆只有2张纸牌可移，这是不是意味着刚才使用的贪心法是错误的呢？,当不具备贪心选择性质时：,得到较优解。,数字三角,如图所示的数字三角形，从顶部出发，在每一结点可以选择向左走或得向右走，一直走到底层，要求找出一条路径，使路径上的值最大。,贪心法：,7+8+1+7+5=28,更优方案：,贪心法：,更优方案：,7+3+8+7+5=30,策略：从第一层开始选，每次选择可选的数字中最大的数字,第二层选择小些的数目能达到更优解,不符合贪心选择性质,分析,当不能100%确定一个贪心算法正确时，在使用之前，就应该尝试证明它的不正确性。要证明其不正确，一种最简单的方法就是举一个反例。其实，要严格证明一个贪心算法的正确性是很困难的，目前最有效的一种方法叫“矩阵胚理论”，但是很复杂。,谢谢,