第二次课动态规划

第二次课动态规划第1页，课件共84页，创作于2023年2月本周POJ上做题：动态规划1037Adecorativefence、1050TotheMax、

1088滑雪、 1125StockbrokerGrapevine、

1141BracketsSequence、 1159Palindrome、

1160PostOffice、 1163TheTriangle、

1458CommonSubsequence、 1579FunctionRunFun、

1887TestingtheCATCHER、 1953WorldCupNoise、

2386LakeCounting第2页，课件共84页，创作于2023年2月

动态规划是1951年由美国数学家贝尔曼（RichardBellman)提出，它是解决一类多阶段决策问题的优化方法，也是考察问题的一种途径。动态规划方法是现代企业管理中的一种重要决策方法。如果一个问题可将其过程划分为若干个相互联系的阶段问题，且它的每一阶段都需进行决策，则这类问题均可用动态规划方法进行求解。根据多阶段决策过程的时序和决策过程的演变，动态规划方法有以下四种类型：离散确定型、离散随机型、连续确定型和连续随机型。第3页，课件共84页，创作于2023年2月几类算法的经典名言动态规划：不做重复的事；贪心法：只选最好的；分支定界法：没戏的就杀掉；回溯法：碰壁就回头。作人生规划要善于利用动态规划；找女朋友要善于利用好贪心算法；人生重大决策要活学活用回溯法；第4页，课件共84页，创作于2023年2月算法总体思想动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=第5页，课件共84页，创作于2023年2月为什么动态规划比递归算法有效？但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次，因此利用递归算法得到的算法往往是指数复杂度的算法。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)T(n/4)T(n)第6页，课件共84页，创作于2023年2月POJ2753Fibonacci数列例子：确定Fibonaccisequencefn项的值:考虑Fibonaccisequence的递归定义:我们将得到如下的递归算法:在POJ上递交之后，返回的结果是：TimeLimited。而不是可爱的ACWhy？第7页，课件共84页，创作于2023年2月子问题的重叠性将上述递归算法展开:可以看出f(n-1)被调用1次,f(n-2)被调用2次,等等.这将导致大量的调用最终解为：第8页，课件共84页，创作于2023年2月树形递归计算过程中存在冗余计算，为了除去冗余计算，可以从已知条件开始计算，并记录计算过程中的中间结果。f(5)f(3)f(2)f(1)f(2)f(4)f(0)f(1)f(0)f(3)f(2)f(1)f(1)f(0)f(1)11001010冗余计算第9页，课件共84页，创作于2023年2月动态规划例：POJ2753Fibonacci数列intf[n+1];f[1]=f[2]=1;intI;for(i=3;i<=n;i++)f[i]=f[i-1]+f[i-2];cout<<f[n]<<endl;用空间换时间第10页，课件共84页，创作于2023年2月动态规划算法的基本要素一、最优子结构一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其为最优子结构性质。同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）例如：最短路径问题。abc在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。第11页，课件共84页，创作于2023年2月动态规划算法的基本要素二、重叠子问题递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。第12页，课件共84页，创作于2023年2月一、例子（最短路问题）假如上图是一个线路网络，两点之间连线上的数字表示两点间的距离（或费用），我们的问题是要将货物从A地运往E地，中间通过B、C、D三个区域，在区域内有多条路径可走，现求一条由A到E的线路，使总距离最短（或总费用最小）。AB1B2B3C1C2C3D1D2E24374632426534633334第13页，课件共84页，创作于2023年2月将该问题划分为4个阶段的决策问题第一阶段为从A到Bj（j=1，2，3），有三种决策方案可供选择；第二阶段为从Bj到Cj（j=1,2,3），也有三种方案可供选择；第三阶段为从Cj到Dj(j=1,2)，有两种方案可供选择；第四阶段为从Dj到E，只有一种方案选择。AB1B2B3C1C2C3D1D2E24374632426534633334第14页，课件共84页，创作于2023年2月如果用完全枚举法，则可供选择的路线有3×3×2×1=18（条），将其一一比较才可找出最短路线：A→B1→C2→D3→E其长度为12。

AB1B2B3C1C2C3D1D2E24374632426534633334第15页，课件共84页，创作于2023年2月显然，这种方法是不经济的，特别是当阶段数很多，各阶段可供的选择也很多时，这种解法甚至在计算机上完成也是不现实的。由于我们考虑的是从全局上解决求A到E的最短路问题，而不是就某一阶段解决最短路线，因此可考虑从最后一阶段开始计算，由后向前逐步推至A点：第16页，课件共84页，创作于2023年2月第四阶段，由D1到E只有一条路线，其长度f4（D1）=3，同理f4（D2）=4。第三阶段，由Cj到Di分别均有两种选择，即，决策点为D1AB1B2B3C1C2C3D1D2E24374632426534633334第17页，课件共84页，创作于2023年2月,决策点为D1，决策点为D2AB1B2B3C1C2C3D1D2E24374632426534633334第18页，课件共84页，创作于2023年2月第二阶段，由Bj到Cj分别均有三种选择，即：决策点为C2

AB1B2B3C1C2C3D1D2E24374632426534633334第19页，课件共84页，创作于2023年2月决策点为C1或C2决策点为C2

AB1B2B3C1C2C3D1D2E24374632426534633334第20页，课件共84页，创作于2023年2月第一阶段，由A到B，有三种选择，即：决策点为B3f1（A）=15说明从A到E的最短距离为12，最短路线的确定可按计算顺序反推而得。即A→B3→C2→D2→E上述最短路线问题的计算过程，也可借助于图形直观的表示出来：AB1B2B3C1C2C3D1D2E24374632426534633334第21页，课件共84页，创作于2023年2月图中各点上方框的数，表示该点到E的最短距离。图中红箭线表示从A到E的最短路线。从引例的求解过程可以得到以下启示：①对一个问题是否用上述方法求解，其关键在于能否将问题转化为相互联系的决策过程相同的多个阶段决策问题。

AB1B2B3C1C2C3D1D2E2437463242653463333434676991112第22页，课件共84页，创作于2023年2月所谓多阶段决策问题是：把一个问题看作是一个前后关联具有链状结构的多阶段过程，也称为序贯决策过程。如下图所示：②在处理各阶段决策的选取上，不仅只依赖于当前面临的状态，而且还要注意对以后的发展。即是从全局考虑解决局部（阶段）的问题。③各阶段选取的决策，一般与“时序”有关，决策依赖于当前的状态，又随即引起状态的转移，整个决策序列就是在变化的状态中产生出来，故有“动态”含义。因此，把这种方法称为动态规划方法。④决策过程是与阶段发展过程逆向而行。第23页，课件共84页，创作于2023年2月拦截导弹（poj1887）某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。第24页，课件共84页，创作于2023年2月输入 输入数据为导弹依次飞来的高度，所有高度值均为不大于30000的正整数。输出 输出只有一行是这套系统最多能拦截的导弹数。第25页，课件共84页，创作于2023年2月输入样例 38920715530029917015865输入样例 6第26页，课件共84页，创作于2023年2月题目分析因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的高度组成一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。第27页，课件共84页，创作于2023年2月设X={x1,x2,…,xn}为依次飞来的导弹序列，Y={y1,y2,…,yk}为问题的最优解（即X的最长非递增子序列），s为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=∞——第一发炮弹能够到达任意的高度）。第28页，课件共84页，创作于2023年2月如果y1=x1，即飞来的第一枚导弹被成功拦截。那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将由s=∞变成s≤x1（x1为第一枚导弹的高度）；第29页，课件共84页，创作于2023年2月在当前状态下，序列Y1={y2,…,yk}也应该是序列X1={x2,…,xn}的最长非递增子序列（大家用反证法很容易证明）。也就是说，在当前状态s≤x1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。这就是拦截导弹问题的最优子结构性质。第30页，课件共84页，创作于2023年2月设D(i)为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截的第i枚）。我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X={x1,x2,…,xn}中的最小值，即第k枚导弹为所有飞来的导弹中高度最低的，则有D(k)=1；当系统拦截了最后一枚导弹xn，那么，系统最多也只能拦截这一枚导弹了，即D(n)=1；其它情况下，也应该有D(i)≥1。第31页，课件共84页，创作于2023年2月根据以上分析，可归纳出问题的动态规划递归方程为：第32页，课件共84页，创作于2023年2月假设系统最多能拦截的导弹数为dmax（即问题的最优值），则dmax（i为被系统拦截的第一枚导弹的顺序号）第33页，课件共84页，创作于2023年2月所以，要计算问题的最优值dmax，需要分别计算出D（1）、D（2）、……D（n）的值，然后将它们进行比较，找出其中的最大值。第34页，课件共84页，创作于2023年2月根据上面分析出来的递归方程，我们完全可以设计一个递归函数，采用自顶向下的方法计算D（i）的值。然后，对i从1到n分别调用这个递归函数，就可以计算出D（1）、D（2）、……D（n）。第35页，课件共84页，创作于2023年2月但这样将会有大量的子问题被重复计算。比如在调用递归函数计算D（1）的时候，可能需要先计算D（5）的值；之后在分别调用递归函数计算D（2）、D（3）、D（4）的时候，都有可能需要先计算D（5）的值。如此一来，在整个问题的求解过程中，D（5）可能会被重复计算很多次，从而造成了冗余，降低了程序的效率。第36页，课件共84页，创作于2023年2月其实，通过以上分析，我们已经知道：D（n）=1。如果将n作为阶段对问题进行划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出D（n-1）、D（n-2）、……D（1）的值。这样，每个D（i）的值只计算一次，并在计算的同时把计算结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。第37页，课件共84页，创作于2023年2月intmain（）{inth[2000],d[2000],count,c,max,i,j;//h表示高度值，d表示最优值，c是能拦截得最多导弹数count=0;while（scanf（"%d",h+count++）!=EOF）; //输入高度d[count-1]=1;c=1;for（i=count-2;i<0;i--）{ //用动态规划计算所有最优值max=0; for（j=i+1;j>count;j++） if（(h[i]>=h[j])&&max<d[j]）max=d[j];d[i]=max+1;if(c<d[i])c=d[i];}printf（"%d\n",c）;}第38页，课件共84页，创作于2023年2月思考题上述问题修改成：要求拦截所有导弹，则需要多少套上述系统？第39页，课件共84页，创作于2023年2月实例POJ2122：FlightPlanning

Yourjobistowriteaprogramthatplansairplaneflights.Eachflightconsistsofaseriesofoneormorelegs.Yourprogrammustchoosethebestaltitudeforeachlegtominimizetheamountoffuelconsumptionduringthetrip.

第40页，课件共84页，创作于2023年2月 Theairplanehasafixedairspeed,givenbytheconstantVCRUISE,andamost-efficientcruisingaltitude,AOPT.WhenflyingataltitudeAOPT,fuelconsumptioningallonsperhourisgivenbyGPHOPT.WhenflyingatanaltitudethatisdifferentfromAOPT,fuelconsumptionincreasesbyGPHEXTRAforeach1000feetaboveorbelowAOPT.第41页，课件共84页，创作于2023年2月 Theflightstartsandfinishesatanaltitudeof0.Each1000footclimbburnsanextraamountoffuelgivenbyCLIMBCOST(thereisnoreductioninfuelconsumptionwhenyoudescend).Maketheapproximationthatallclimbinganddescendingisdoneinzerotimeatthebeginningofeachflightleg.第42页，课件共84页，创作于2023年2月 Thuseachlegisflownataconstantairspeedandaltitude.Forthisproblem,theairplanecharacteristicsaregivenbythefollowingconstants:第43页，课件共84页，创作于2023年2月

VCRUISE400knots(aknotisonenauticalmile(1.852km)perhour)

AOPT30,000feet GPHOPT2000gallonsperhour GPHEXTRA10gallonsperhourforeach1000feet CLIMBCOST50gallonsper1000feetofclimb第44页，课件共84页，创作于2023年2月 Beforeeachflight,youaregiventhelengthofeachlegandthetailwindexpectedforeachleg.Apositivetailwindincreasestheairplane’sspeedovertheground,andanegativetailwinddecreasesitsspeedovertheground. Forexample,ifairspeedis400knotsandthetailwindis-50knots,speedoverthegroundis350knots.第45页，课件共84页，创作于2023年2月Bypolicy,altitudeforeachlegmustbesomeintegermultipleof1000feet,between20,000and40,000feet,inclusive.Yourprogrammustcomputethebestaltitudeforeachlegtominimizeoverallfuelconsumptionforthetrip,andmustcomputethefuelrequiredforthetrip.第46页，课件共84页，创作于2023年2月Input ThefirstlinecontainsanintegerN,representingthenumberofflightsyouarerequiredtoplan.Eachflightconsistsofthefollowinginputlines: ThefirstinputlineinaflightcontainsanintegerK(0<K<10),representingthenumberoflegsintheflight.ThenextKinputlineseachcontainthefollowingthreeintegers: (1)Thelengthoftheleg,innauticalmiles (2)Theexpectedtailwindat20,000feet,inknots (3)Theexpectedtailwindat40,000feet,inknots第47页，课件共84页，创作于2023年2月Theexpectedtailwindataltitudesbetween20,000and40,000feetiscomputedbylinearinterpolation.Forexample,theexpectedtailwindat30,000feetishalfwaybetweentheexpectedtailwindat20,000feetandtheexpectedtailwindat40,000feet.第48页，课件共84页，创作于2023年2月Output Yourprogrammustproduceoneoutputlineforeachflight.Theoutputlinemustcontaintheflightnumber(countingfromthebeginningoftheproblem),thechosenaltitudeforeachleg(inthousandsoffeet),andthefuelrequiredforthetrip(ingallons,tothenearestgallon).第49页，课件共84页，创作于2023年2月SampleInput221500-50501000003100050020000201800-50100OutputfortheSampleInputFlight1:353013985Flight2:20304023983第50页，课件共84页，创作于2023年2月图例：第51页，课件共84页，创作于2023年2月转换为多段图问题FlightPlan可以转换为多段图问题，每一条边代表某段由前一段飞行高度飞到本段的某一飞行高度的燃油消耗量第52页，课件共84页，创作于2023年2月Analysis一、计算飞机在地域i的耗油量假设飞机在地域i-1（2≤i≤k+1）的海拔高度为l，飞到地域i的海拔高度为m，计算飞机在地域i的耗油量g[i,l,m]必须考虑如下几个因素：（注意：为了方便计算，飞行高度和风速以1000feet为单位）1.上升过程增加的耗油量a由于飞机每上升一个单位，需要增加climbcost的耗油量，因此

第53页，课件共84页，创作于2023年2月Analysis2.每小时的实际耗油量b飞机在海拔高度aopt飞行时每小时耗油gphopt.当飞机在m高度飞行时，与aopt的垂直距离为个单位。每垂直偏离aopt高度一个单位，需要增加耗油量gphextra.因此第54页，课件共84页，创作于2023年2月3.在地域i的实际飞行时间cc=地域i的长度/地域i的实际飞行速度由于地域i的风速垂直反向线性变化，m单位处的风速为在20单位处的风速与40单位处的风速的平均数，因此地域i的等高风速为

第55页，课件共84页，创作于2023年2月而飞机的实际速度为VCRUISE与地域i等高风速的矢量和，因此c=地域i的长度/(地域i的等高风速＋VCRUISE)显而易见，第56页，课件共84页，创作于2023年2月二．规划飞行方案

设为在确定地域i的飞行高度为j的情况下，飞机由地域l飞至地域i所耗费的最小总耗油量；为记忆表。飞机由地域i-l的高度到达地域i的j高度，可使总耗油量最小，即

第57页，课件共84页，创作于2023年2月问题是怎么才能计算呢？首先我们必须明确，按最优性要求确定了飞机在地域i-1的飞行为高度为; 由于为一个定值，因此的值必须最小。不然的话，将它替换到表达式中，则可使表达式值变得更小，出现矛盾，这就说明问题的最优解包含了子问题的最优解，即该问题具备了最优子结构。第58页，课件共84页，创作于2023年2月

下面我们来分析一下最优表达式的构造：飞机由地域1起飞，因此data[1,j]=g[1,0,j](20≤j≤40).然后顺序计算， data[2,20]…data[2,40],data[3,20],…,data[3,40],.....data[k,20],…,data[k,40].第59页，课件共84页，创作于2023年2月

在计算data[i,j]时，我们无法预计飞机在地域i-1应以怎样的高度飞行方可使表达式的值最小。因此只能一一假设飞机在地域i-1的高度为20,21,…,40,即分别求出从上述21个表达式中选出值最小的一个，即：将满足上式的飞行高度L存入记忆表data2[i,j]第60页，课件共84页，创作于2023年2月

由此可见，在求data[i,j]的过程中不断查阅子问题的解data[i-1,20]...data[i-1,40]。显然这个最优化问题包含了重叠子问题，采用动态程序设计方法是最合适不过的了，按照上述分析，我们可以直接写出动态规划的方程：1≤i≤k20≤j≤4020≤l≤40第61页，课件共84页，创作于2023年2月

求解data表和data2表的算法十分简单：forj:=20to40dodata[1,j]←g[1,0,j];/*构造记忆表*/fori:=2tokdoforj:=20to40dofori:=20to40dobegin计算data[i,j]=min{data[i-1,l],g[i,l,j]};将满足上式的l记入记忆表data2[i,j];end:{for}第62页，课件共84页，创作于2023年2月三.输出飞行计划有了记忆表data2我们便可以从地域k出发倒推飞机在各地域的飞行高度data3:

forj:=20to40dodata3[k]←计算满足min{data[k,j]}的j;fori:=kdownto2dodata3[i-l]←data2{i,data3[i]};最后输出飞行计划：fori=1tokdo输出飞机在地域i的飞行高度data3[i];输出最小的总耗油量data[k,data3[k]];

每输入一条航线信息，我们便使用上述方法规划该航线的飞行方案，直至n条航线规划完毕第63页，课件共84页，创作于2023年2月Uxuhul的表决Uxuhul印第安人是世界上最古老的文明之一。在中美洲丛林中，大约从公元前3200年的黄金时代，Uxuhul文化繁荣了近千年。每年代表各阶层的高级牧师都会聚集在首都，投票表决重要事情。每次严格限定表决三个议案，每个议案只有是/否的回答。三个议案在议论表决中同时决定，遵循下列形式：第64页，课件共84页，创作于2023年2月所有牧师聚集在一大房间，房间中央有一张桌子。在桌子上放了三片石块，一面黑，一面白。每个石块代表一个议案，黑表示“否”，白表示“是”。最初所有的石块都是黑色的面朝上，表示所有的议案都是否定的结果。根据年龄，从年轻的到年长者，每位牧师通过翻动一块石块来表决，也就是改变某个议案的结果。不允许不表决。最年长的牧师做出选择后，石块朝上的颜色决定了三个议案的最终结果。第65页，课件共84页，创作于2023年2月Uxuhul的政治相当复杂，大量代表不同利益的游说（和行贿），影响三个议案的八种结果。宗教规则强制每位牧师在投票表决前公开他们对三个议案的八种结果的表决倾向。由于彼此间都知道表决倾向，每位牧师都争取对自己最有利的结果，而且Uxuhul人具有高超的逻辑推理能力，对游戏规则又很了解，每个牧师都能找到最理想的方法！第66页，课件共84页，创作于2023年2月最后，复杂刻板行政系统导致Uxuhul文明的崩溃。只留下他们的城市和庙宇，历史学家和考古学家试图通过研究每年议案的表决结果来弄清他们的历史。不管怎么说，只有牧师们的表决倾向留下来了，没有实际的表决结果。那么你的任务就是揭示出表决结果。第67页，课件共84页，创作于2023年2月输入输入从一个整数n开始,1<=n<=100，代表表决的次数。后面跟着n个问题。每次表决由一个整数m开始，1<=m<=100，表示牧师的数目。后面m行，按照顺序代表每位投票者的表决倾向。对于每种结果（NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY,‘N’表示否，‘Y’表示是）,给一个[1…8]之间的数，越小的数字表示选择可能性越大。对8种结果的表决倾向按照前面列举的顺序的给出。第68页，课件共84页，创作于2023年2月输出对于每个问题，输出三个议案的表决结果。‘N’表示否，‘Y’表示是。第69页，课件共84页，创作于2023年2月输入样例2487654321863124578365127412345678112345678第70页，课件共84页，创作于2023年2月输出样例NYYNNY第71页，课件共84页，创作于2023年2月解题思路这个题似乎可以采用贪心来做。每一个牧师都从可能的结果中选择对自己最有利的结果，最后的结果似乎就是人人都满意的结果？仔细分析就发现这种思路不正确。假如有两个人来选择，选择倾向是：2174583638645127第72页，课件共84页，创作于2023年2月如果按照贪心的思想去做，第一个人应该选择NNY,但第二个人肯定会选择成YNY，结果是第一个人最不满意的。如果第一个人选择NYN，表面上是他不满意的选择（排在第七位的结果），但第二个人会选择YYN（这是他在这种情况下的最好选择，排在第二位）,而对于第一个人来说，YYN也是一个不错的结果。第73页，课件共84页，创作于2023年2月所以，贪心的思路不行。在解决这个题之前，让我们先看看海盗的传说：第74页，课件共84页，创作于2023年2月有5个海盗，多年的海上生活使他们积攒了100颗宝石。他们决定将宝石分掉之后就分手，洗手不干了。他们商量许久，最后决定：首先抽签，每个人抽得一个号码（1号到5号），然后1号海盗提出一个分配方案，所有海盗举手表决，如果过半数的海盗同意该分配方案，则按此方案分配，否则将1号海盗扔到大海。再由2号海盗提出他的分配方案，重复以上过程，直到找到分配方案止。海盗都是很聪明的，而且彼此知道别人的聪明，每个海盗都希望得到最多的宝石。如果你是1号海盗，你会提出怎样的分配方案，使你获得最多的宝石且保住性命？第75页，课件共84页，创作于2023年2月因为海盗很聪明，所以你能想到的别的也能想到。我们从简单情况出发：首先看4号海盗分配方案，只可能是0100（少1颗5号可不会投票支持）所以3号海盗分配方案，9910（首先5号一颗都不用给，因为只有100颗才能合他的胃口，4号一颗足矣，总比没有强）第76页，课件共84页，创作于2023年2月2号海盗分配方案，97021（首先3号一颗都不用给，因为只有100颗才能合他的胃口，4号两颗，5号一颗，要比3号分得多）所以1号海盗最佳分配方案，970102（原因同上，1，3，5号海盗投票支持）第77页，课件共84页，创作于2023年2月和海盗问题一样，要倒过来思考，我们以杨例中的第一组数据来说明牧师是怎么思考的487654321863124578365127412345678第78页，课件共84页，创作于2023年2月首先最后投票的很简单，从可能出现的结果里找个最喜欢的。倒数第二怎么投？假设他面对的是NYY，他可以变为{NNY，NYN，YYY}，这其中他最喜欢的是NNY，但他就会选择NNY吗？不会！因为选择NNY，最后（通过最后牧师表决）的结果就是NNN，是他最不喜欢的，他的选择是YYY，因为最后的结果将是NYY，是可以得到的最好结果。从后往前，记录当前祭司面对每种情况（NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY）下选择能得到的最好结果。倒数第二个：836