普及讲座6基于贪心的算法和应用举例C版.pptx

江苏省大丰高级中学江苏省大丰高级中学 陈鹏陈鹏Peng ChenPeng Chen JiangSu DaFeng Senior High School JiangSu DaFeng Senior High School基于贪心的算法和应用举例GreedyGreedySelector Selector AlgorithmAlgorithm&A&Applicationpplication一贪心策略二应用举例三小结15 四月四月 20242一贪心策略引例引例1 1删数问题删数问题 键盘输入一个高精度的正整数键盘输入一个高精度的正整数n n（n=240n=240），去），去掉其中任意掉其中任意s s个数字后剩下的数字按原左右次序将组个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的成一个新的正整数。编程对给定的n n和和s s，寻找一种方，寻找一种方案，使得剩下的数字组成的新数最小。案，使得剩下的数字组成的新数最小。【算法分析算法分析】每一步总是选择一个使剩下的数最小的数字删去，每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符。除最后一个数字；否则删除第一个递减区间的首字符。15 四月四月 20243一贪心策略定义定义贪心贪心 贪心算法是从问题的某一个初始状态出发，通过贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。过这种方法产生出一个全局最优解的方法。小球表示当前状态；小球表示当前状态；红箭头表示当前最优决策；红箭头表示当前最优决策；蓝箭头表示其他决策。蓝箭头表示其他决策。15 四月四月 20244方向方向一贪心策略 贪心标准选择贪心标准选择：所谓贪心标准选择就是应用当前：所谓贪心标准选择就是应用当前“最好最好”的标准作为统一标准，将原问题变为一个相的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。似最佳的选择。最优子结构最优子结构：当一个问题的最优解包含其子问题：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。的最优解时，称此问题具有最优子结构性质。15 四月四月 20245一贪心策略引例引例2 2金银岛金银岛 某天某天KIDKID利用飞行器飞到了一个金银岛上，上面利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，有许多珍贵的金属，KIDKID喜欢各种宝石的艺术品，可喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为口袋至多只能装重量为w w的物品。岛上金属有的物品。岛上金属有s s个种类个种类,每种金属重量不同，分别为每种金属重量不同，分别为n n1 1，n n2 2，n ns s，同时，同时每个种类的金属总的价值也不同，分别为每个种类的金属总的价值也不同，分别为v v1 1，v v2 2，v vs s。KIDKID想一次带走价值尽可能多的金属，问他最想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。多能带走价值多少的金属。注意注意到金属是可以被任意到金属是可以被任意分割的，并且金属的价值和其重量成正比。分割的，并且金属的价值和其重量成正比。15 四月四月 20246一贪心策略【算法分析算法分析】有以下几种策略可供选择：有以下几种策略可供选择：（1 1）每次挑选价值最大的物品装入背包，得到的）每次挑选价值最大的物品装入背包，得到的结果是否最优？结果是否最优？（2 2）每次挑选所占重量最小的物品装入是否能得）每次挑选所占重量最小的物品装入是否能得到最优解？到最优解？（3 3）每次选取单位重量价值最大的物品。）每次选取单位重量价值最大的物品。15 四月四月 20247一贪心策略 解题一般步骤解题一般步骤:1 1、设计数据找规律；、设计数据找规律；2 2、进行贪心猜想；、进行贪心猜想；3 3、正确性证明（严格证明和一般证明）、正确性证明（严格证明和一般证明）一般证明一般证明：列举反例；：列举反例；严格证明严格证明：数学归纳和反证法；：数学归纳和反证法；4 4、程序实现。、程序实现。15 四月四月 20248二应用举例例例1 1三国游戏三国游戏【问题描述问题描述】小涵很喜欢一个叫做三国的游戏。在游戏中，小涵小涵很喜欢一个叫做三国的游戏。在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共和计算机各执一方，组建各自的军队进行对战。游戏中共有有N N位武将（位武将（N N为偶数且不小于为偶数且不小于4 4），任意两个武将之间有一），任意两个武将之间有一个个“默契值默契值”，表示若此两位武将作为一对组合作战时，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。从自由武将中选出一个加入计算机方的军队。15 四月四月 20249二应用举例 接下来一直按照接下来一直按照“小涵小涵计算机计算机小涵小涵”的顺序选的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。获胜，表示两军交战，拥有获胜武将组合的一方获胜。已知计算机一方选择武将的原则是尽量破坏对手下一步已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己最高的那对武将组合，并将该组合中的自由武将选入自己的军队。的军队。15 四月四月 202410二应用举例 下面举例说明计算机的选将策略，例如，游戏中下面举例说明计算机的选将策略，例如，游戏中一共有一共有6 6个武将，他们相互之间的默契值如下表所示个武将，他们相互之间的默契值如下表所示 双方选将过程如下所示：双方选将过程如下所示：15 四月四月 202411武将相互之间的默契值：武将相互之间的默契值：双方选将过程入图所示：双方选将过程入图所示：二应用举例 小涵想知道，如果计算机在一局游戏中始终坚持小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？组合的默契值最大是多少？假设整个游戏过程中，对战双方任何时候均能看假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。问题，保证对于不同的武将组合，其默契值均不相同。15 四月四月 202412二应用举例【算法分析算法分析】由于计算机的贪心策略，每一个武将不可能与和由于计算机的贪心策略，每一个武将不可能与和他默契度最大的武将合作，但要与和他默契度次大的他默契度最大的武将合作，但要与和他默契度次大的武将合作，变得非常容易，小涵只需要经过两次挑选。武将合作，变得非常容易，小涵只需要经过两次挑选。只要小涵选出默契度次大值中最大的那对武将，只要小涵选出默契度次大值中最大的那对武将，那么他将稳操胜券。那么他将稳操胜券。15 四月四月 202413二应用举例15 四月四月 202414123456152816292722332013832264331151261654323332二应用举例15 四月四月 20241512345678111111170211118013111501416011511161171818765432二应用举例15 四月四月 20241612345678111111170211118013111114160501511161171818765432二应用举例【算法分析算法分析】将所有边按从大到小排序，检查每条边的两个顶将所有边按从大到小排序，检查每条边的两个顶点是否已出现过，有三种情况：点是否已出现过，有三种情况：（1 1）两个顶点都没有出现过，说明两个武将都是）两个顶点都没有出现过，说明两个武将都是自由的，不能同时取到，放弃该边；自由的，不能同时取到，放弃该边；（2 2）有一个顶点出现过，说明这个武将前面可以）有一个顶点出现过，说明这个武将前面可以被小涵先取到，现在可以取另一个顶点，该边即为最被小涵先取到，现在可以取另一个顶点，该边即为最大值；大值；（3 3）两个顶点都出现过，说明这两个武将前面都）两个顶点都出现过，说明这两个武将前面都可以被小涵分别先取到，该边即为最大值。可以被小涵分别先取到，该边即为最大值。15 四月四月 202417二应用举例【参考程序片断参考程序片断】const int N=505;const int N=505;inline int read()inline int read()char c=getchar();int x=0,f=1;char c=getchar();int x=0,f=1;while(c9)if(c=-)f=-1;c=getchar();while(c9)if(c=-)f=-1;c=getchar();while(c=0&c=0&c=9)x=x*10+c-0;c=getchar();return x*f;return x*f;int n,m,ans,aNN;int n,m,ans,aNN;int main()int main()n=read();n=read();for(int i=1;i=n;i+)for(int i=1;i=n;i+)for(int j=i+1;j=n;j+)aij=aji=read();for(int j=i+1;j=n;j+)aij=aji=read();15 四月四月 202418二应用举例 for(int i=1;i=n;i+)for(int i=1;i=n;i+)int t1=0,t2=0;int t1=0,t2=0;for(int j=1;j=n;j+)for(int j=1;jt1)t2=t1,t1=aij;if(aijt1)t2=t1,t1=aij;else if(aijt2)t2=aij;else if(aijt2)t2=aij;ans=max(ans,t2);ans=max(ans,t2);printf(1n%d,ans);printf(1n%d,ans);15 四月四月 202419二应用举例例例2 2推销员推销员【问题描述问题描述】阿明是一名推销员，他奉命到螺丝街推销他们公司的产阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有一侧是围墙，另一侧是住户。螺丝街一共有N N家住户，第家住户，第i i家住户到入口的距离为家住户到入口的距离为S Si i米。由于同一栋房子里可以有多家米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的入口进入，依次向螺丝街的X X家住户推销产品，然后再原路家住户推销产品，然后再原路走出去。走出去。阿明每走阿明每走1 1米就会积累米就会积累1 1点疲劳值，向第点疲劳值，向第i i家住户推销产品家住户推销产品会积累会积累A Ai i点疲劳值。阿明是工作狂，他想知道，对于不同的点疲劳值。阿明是工作狂，他想知道，对于不同的X X，在不走多余的路的前提下，他最多可以积累多少点疲劳，在不走多余的路的前提下，他最多可以积累多少点疲劳值。值。15 四月四月 202420二应用举例【输入格式】【输入格式】第一行第一行为一个正整数为一个正整数N N，表示螺丝街住户的数量。，表示螺丝街住户的数量。接下来的一行接下来的一行为为N N个正整数，其中个正整数，其中：第：第i i个整数个整数S Si i表示第表示第i i家住户到入口的距离。数据保证家住户到入口的距离。数据保证S S1 1=S=S2 2=S=Sn n108108。接下来的一行接下来的一行为为N N个正整数，其中个正整数，其中：第：第i i个整数个整数A Ai i表示向表示向第第i i户住户推销产品会积累的疲劳值。数据保证户住户推销产品会积累的疲劳值。数据保证A Ai i103103。【输出格式】【输出格式】输出输出N N行，每行一个正整数，第行，每行一个正整数，第i i行整数表示当行整数表示当X=iX=i时，阿时，阿明最多积累的疲劳值。明最多积累的疲劳值。15 四月四月 202421二应用举例【输入【输入输出样例输出样例】输入：输入：输出：输出：5 155 151 2 3 4 5 191 2 3 4 5 191 2 3 4 5 221 2 3 4 5 22 24 24 25 2515 四月四月 202422二应用举例【样例说明样例说明】15 四月四月 202423S S 1 2 3 4 51 2 3 4 5 A A 1 2 3 4 51 2 3 4 5起点起点疲疲劳值 1 1S S 1 2 3 4 51 2 3 4 5 A A 1 2 3 4 51 2 3 4 5起点起点疲疲劳值 1 2 3 41 2 3 4二应用举例15 四月四月 202424S S 1 2 3 4 51 2 3 4 5 A A 1 2 3 4 51 2 3 4 5起点起点疲疲劳值 1 2 31 2 3S S 1 2 3 4 51 2 3 4 5 A A 1 2 3 4 51 2 3 4 5起点起点疲疲劳值 1 21 2二应用举例【算法分析算法分析】题目中所说不走多余路的意思就是推销题目中所说不走多余路的意思就是推销x x的房子的时候的房子的时候必须一口气走完，不能绕来绕去，这样就更能说明了这样必须一口气走完，不能绕来绕去，这样就更能说明了这样的贪心策略是可以的。的贪心策略是可以的。如何选取当前那一个疲劳值最大的房子呢？对于一个没如何选取当前那一个疲劳值最大的房子呢？对于一个没来过的房子（偏向右端），价值就是来过的房子（偏向右端），价值就是si*2+aisi*2+ai，这里指，这里指的是第一个，接下来就不一样了，每一次接下来选择的都的是第一个，接下来就不一样了，每一次接下来选择的都是阿明走过最远房子的左端或右端中价值最大的房子。对是阿明走过最远房子的左端或右端中价值最大的房子。对于左端，因为不能走多余的路，所以价值就是于左端，因为不能走多余的路，所以价值就是aiai，右端，右端呢，需要加上往返的距离，所以价值就是呢，需要加上往返的距离，所以价值就是ai+(si-ai+(si-now)*2now)*2，其中，其中nownow指的就是阿明走过最远房子的位置，然后指的就是阿明走过最远房子的位置，然后取一个最大值即可。取一个最大值即可。15 四月四月 202425二应用举例【算法分析算法分析】贪心策略贪心策略：每次访问的位置每次访问的位置maxmax(maxmax(已访问的最远位置的已访问的最远位置的左边疲劳值左边疲劳值)，max(max(已访问的最远位置到某个位置距已访问的最远位置到某个位置距离离*2+2+疲劳值疲劳值)。15 四月四月 202426起点起点已已访问的的最最远位置位置疲疲劳值距离距离*2+*2+疲疲劳值二应用举例【参考程序片断参考程序片断】right=0;ri=ri-1+max;fsel=false;right=0;ri=ri-1+max;fsel=false;for(i=1;iright right=sel;for(i=1;iright right=sel;max:=0;coutri;max:=0;coutri;for(j=1;i=right-1;j+)for(j=1;imax)if fj&(ajmax)max=aj;sel=j;max=aj;sel=j;for(j=right+1;j=n;j+)for(j=right+1;jmax)if fj&(aj+(sj-sright)*2max)max=aj+(sj-sright)*2;sel=j;max=aj+(sj-sright)*2;sel=j;15 四月四月 202427二应用举例例例3 3电池的寿命电池的寿命【问题描述问题描述】小小S S新买了一个掌上游戏机，这个游戏机由两节新买了一个掌上游戏机，这个游戏机由两节5 5号电池号电池供电。为了保证能够长时间玩游戏，他买了很多供电。为了保证能够长时间玩游戏，他买了很多5 5号电池，号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用有所不同，有的能使用5 5个小时，有的可能就只能使用个小时，有的可能就只能使用3 3个个小时。显然如果他只有两个电池一个能用小时。显然如果他只有两个电池一个能用5 5小时一个能用小时一个能用3 3小时，那么他只能玩小时，那么他只能玩3 3个小时的游戏，有一个电池剩下的电个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用地利用它们，比如他有三个电池分别能用3 3、3 3、5 5小时，他小时，他可以先使用两节能用可以先使用两节能用3 3个小时的电池，使用半个小时后再把个小时的电池，使用半个小时后再把其中一个换成能使用其中一个换成能使用5 5个小时的电池，两个半小时后个小时的电池，两个半小时后15 四月四月 202428二应用举例再把剩下的一节电池换成刚才换下的电池（那个电池还能用再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.52.5个小时），这样总共就可以使用个小时），这样总共就可以使用5.55.5个小时，没有一点个小时，没有一点浪费。浪费。现在已知电池的数量和电池能够使用的时间，请你找一现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。种方案使得使用时间尽可能的长。15 四月四月 202429二应用举例【输入格式】【输入格式】输入包含多组测试数据。输入包含多组测试数据。每组测试数据包括两行，第一行为一个整数每组测试数据包括两行，第一行为一个整数N N（2=N=10002=Nn;cinn;max=-maxlongint;/max=-maxlongint;/最大的电池容量最大的电池容量sum=0;/sum=0;/电池总容量电池总容量for(i=1;i=n;i+)for(i=1;ix;cinx;sum=sum+x;sum=sum+x;if xmax max=x;if xmax max=x;sum=sum-max;sum=sum-max;if summax coutmax cout(sum+max)/2);else cout(sum*1.0);else cout(sum*1.0);15 四月四月 202433三小结1 1、贪心算法的核心问题是选择能产生问题最优解的最、贪心算法的核心问题是选择能产生问题最优解的最优度量标准，即具体的贪心策略。优度量标准，即具体的贪心策略。2 2、特点是快，在运行过程中无回溯过程，每一步都是、特点是快，在运行过程中无回溯过程，每一步都是当前的最佳选择。当前的最佳选择。3 3、难点是如何贪心和证明贪心的正确性，即如何用一、难点是如何贪心和证明贪心的正确性，即如何用一个小规模的解构造更大规模的解。个小规模的解构造更大规模的解。4 4、比赛过程中，需要胆大心细地归纳、分析。、比赛过程中，需要胆大心细地归纳、分析。15 四月四月 202434