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

江苏省大丰高级中学陈鹏PengChenJiangSuDaFengSeniorHighSchool基于贪心的算法和应用举例

GreedySelectorAlgorithm&Application[一]贪心策略

[二]应用举例

[三]小结10六月20232[一]贪心策略『引例1』——删数问题键盘输入一个高精度的正整数n（n<=240），去掉其中任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【算法分析】每一步总是选择一个使剩下的数最小的数字删去，即按高位到低位的顺序搜索，若各位数字递增，则删除最后一个数字；否则删除第一个递减区间的首字符。10六月20233[一]贪心策略『定义』——贪心贪心算法是从问题的某一个初始状态出发，通过逐步构造最优解的方法向给定的目标前进，并期望通过这种方法产生出一个全局最优解的方法。小球表示当前状态；红箭头表示当前最优决策；蓝箭头表示其他决策。10六月20234方向[一]贪心策略

贪心标准选择：所谓贪心标准选择就是应用当前“最好”的标准作为统一标准，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前看似最佳的选择。

最优子结构：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。10六月20235[一]贪心策略『引例2』——金银岛某天KID利用飞行器飞到了一个金银岛上，上面有许多珍贵的金属，KID喜欢各种宝石的艺术品，可是也不拒绝这样珍贵的金属。但是他只带着一个口袋，口袋至多只能装重量为w的物品。岛上金属有s个种类,每种金属重量不同，分别为n1，n2，…，ns，同时每个种类的金属总的价值也不同，分别为v1，v2，…，vs。KID想一次带走价值尽可能多的金属，问他最多能带走价值多少的金属。注意到金属是可以被任意分割的，并且金属的价值和其重量成正比。10六月20236[一]贪心策略【算法分析】有以下几种策略可供选择：（1）每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占重量最小的物品装入是否能得到最优解？（3）每次选取单位重量价值最大的物品。10六月20237[一]贪心策略解题一般步骤:1、设计数据找规律；2、进行贪心猜想；3、正确性证明（严格证明和一般证明）★一般证明：列举反例；★严格证明：数学归纳和反证法；4、程序实现。10六月20238[二]应用举例『例1』——三国游戏【问题描述】小涵很喜欢一个叫做《三国》的游戏。在游戏中，小涵和计算机各执一方，组建各自的军队进行对战。游戏中共有N位武将（N为偶数且不小于4），任意两个武将之间有一个“默契值”，表示若此两位武将作为一对组合作战时，该组合的威力有多大。游戏开始前，所有武将都是自由的（称为自由武将，一旦某个自由武将被选中作为某方军队的一员，那么他就不再是自由武将了），换句话说，所谓的自由武将不属于任何一方。游戏开始，小涵和计算机要从自由武将中挑选武将组成自己的军队，规则如下：小涵先从自由武将中选出一个加入自己的军队，然后计算机也从自由武将中选出一个加入计算机方的军队。10六月20239[二]应用举例接下来一直按照“小涵→计算机→小涵→…”的顺序选择武将，直到所有的武将被双方均分完。然后，程序自动从双方军队中各挑出一对默契值最高的武将组合代表自己的军队进行二对二比武，拥有更高默契值的一对武将组合获胜，表示两军交战，拥有获胜武将组合的一方获胜。已知计算机一方选择武将的原则是尽量破坏对手下一步将形成的最强组合，它采取的具体策略如下：任何时刻，轮到计算机挑选时，它会尝试将对手军队中的每个武将与当前每个自由武将进行一一配对，找出所有配对中默契值最高的那对武将组合，并将该组合中的自由武将选入自己的军队。10六月202310[二]应用举例下面举例说明计算机的选将策略，例如，游戏中一共有6个武将，他们相互之间的默契值如下表所示双方选将过程如下所示：10六月202311武将相互之间的默契值：双方选将过程入图所示：[二]应用举例小涵想知道，如果计算机在一局游戏中始终坚持上面这个策略，那么自己有没有可能必胜？如果有，在所有可能的胜利结局中，自己那对用于比武的武将组合的默契值最大是多少？假设整个游戏过程中，对战双方任何时候均能看到自由武将队中的武将和对方军队的武将。为了简化问题，保证对于不同的武将组合，其默契值均不相同。10六月202312[二]应用举例【算法分析】由于计算机的贪心策略，每一个武将不可能与和他默契度最大的武将合作，但要与和他默契度次大的武将合作，变得非常容易，小涵只需要经过两次挑选。

只要小涵选出默契度次大值中最大的那对武将，那么他将稳操胜券。10六月202313[二]应用举例10六月202314123456152816292722332013832264331151261654323332[二]应用举例10六月20231512345678111111170211118013111501416011511161171818765432[二]应用举例10六月20231612345678111111170211118013111114160501511161171818765432[二]应用举例【算法分析】将所有边按从大到小排序，检查每条边的两个顶点是否已出现过，有三种情况：（1）两个顶点都没有出现过，说明两个武将都是自由的，不能同时取到，放弃该边；（2）有一个顶点出现过，说明这个武将前面可以被小涵先取到，现在可以取另一个顶点，该边即为最大值；（3）两个顶点都出现过，说明这两个武将前面都可以被小涵分别先取到，该边即为最大值。10六月202317[二]应用举例【参考程序片断】constintN=505;inlineintread(){charc=getchar();intx=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}returnx*f;}intn,m,ans,a[N][N];intmain(){n=read();for(inti=1;i<=n;i++)for(intj=i+1;j<=n;j++)a[i][j]=a[j][i]=read();10六月202318[二]应用举例

for(inti=1;i<=n;i++){intt1=0,t2=0;for(intj=1;j<=n;j++){if(a[i][j]>t1)t2=t1,t1=a[i][j];elseif(a[i][j]>t2)t2=a[i][j];}ans=max(ans,t2);}

printf("1\n%d",ans);}10六月202319[二]应用举例『例2』——推销员【问题描述】阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销产品，然后再原路走出去。阿明每走1米就会积累1点疲劳值，向第i家住户推销产品会积累Ai点疲劳值。阿明是工作狂，他想知道，对于不同的X，在不走多余的路的前提下，他最多可以积累多少点疲劳值。10六月202320[二]应用举例【输入格式】第一行为一个正整数N，表示螺丝街住户的数量。接下来的一行为N个正整数，其中：第i个整数Si表示第i家住户到入口的距离。数据保证S1<=S2<=…<=Sn<10^8。接下来的一行为N个正整数，其中：第i个整数Ai表示向第i户住户推销产品会积累的疲劳值。数据保证Ai<10^3。【输出格式】输出N行，每行一个正整数，第i行整数表示当X=i时，阿明最多积累的疲劳值。10六月202321[二]应用举例【输入输出样例】输入：输出：51512345191234522242510六月202322[二]应用举例【样例说明】10六月202323S

12345

A

12345起点疲劳值1S

12345

A

12345起点疲劳值1234[二]应用举例10六月202324S

12345

A

12345起点疲劳值123S

12345

A

12345起点疲劳值12[二]应用举例【算法分析】题目中所说不走多余路的意思就是推销x的房子的时候必须一口气走完，不能绕来绕去，这样就更能说明了这样的贪心策略是可以的。如何选取当前那一个疲劳值最大的房子呢？对于一个没来过的房子（偏向右端），价值就是s[i]*2+a[i]，这里指的是第一个，接下来就不一样了，每一次接下来选择的都是阿明走过最远房子的左端或右端中价值最大的房子。对于左端，因为不能走多余的路，所以价值就是a[i]，右端呢，需要加上往返的距离，所以价值就是a[i]+(s[i]-now)*2，其中now指的就是阿明走过最远房子的位置，然后取一个最大值即可。10六月202325[二]应用举例【算法分析】

贪心策略：每次访问的位置＝max{max(已访问的最远位置的左边疲劳值)，max(已访问的最远位置到某个位置距离*2+疲劳值)}。10六月202326起点已访问的最远位置疲劳值距离*2+疲劳值[二]应用举例【参考程序片断】right=0;r[i]=r[i-1]+max;f[sel]=false;for(i=1;i<=n;i++){ifsel>rightright=sel;max:=0;cout<<r[i];for(j=1;i<=right-1;j++)}iff[j]&&(a[j]>max){max=a[j];sel=j;}for(j=right+1;j<=n;j++)iff[j]&&(a[j]+(s[j]-s[right])*2>max){max=a[j]+(s[j]-s[right])*2;sel=j;}10六月202327[二]应用举例『例3』——电池的寿命【问题描述】小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后10六月202328[二]应用举例再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。10六月202329[二]应用举例【输入格式】输入包含多组测试数据。每组测试数据包括两行，第一行为一个整数N（2<=N<=1000），表示电池的数目。接下来的一行为N个正整数，表示电池能使用的时间。【输出格式】对每组数据输出一行，表示电池能使用的时间，结果保留到小数点后1位。10六月202330[二]应用举例【输入输出样例】输入：输出：23.035