1、第五章动态规划第五章动态规划1 海盗分金问题海盗分金问题 5名海盗抢得了窖藏的100块金子，并打算瓜分这些战利品。这是一些讲民主的海盗（当然是他们自己特有的民主），他们的习惯是按下面的方式进行分配：最厉害的一名海盗提出分配方案，然后所有的海盗（包括提出方案者本人）就此方案进行表决。如果50%或更多的海盗赞同此方案，此方案就获得通过并据此分配战利品。否则提出方案的海盗将被扔到海里，然后下一名最厉害的海盗又重复上述过程。所有的海盗都乐于看到他们的一位同伙被扔进海里，不过，如果让他们选择的话，他们还是宁可得一笔现金。他们当然也不愿意自己被扔到海里。所有的海盗都是聪明绝顶的，而且知道其他的海盗也是聪明
2、绝顶的。此外，没有两名海盗是同等厉害的这些海盗按照完全由上到下的等级排好了座次，并且每个人都清楚自己和其他所有人的等级。这些金块不能再分，也不允许几名海盗共有金块，因为任何海盗都不相信他的同伙会遵守关于共享金块的安排。这是一伙每人都只为自己打算的海盗。最凶的一名海盗应当提出什么样的分配方案才能使他获得最多的金子呢？我们按照这些海盗的威望值来给他们编号。最怯懦的海盗为1，最厉害的海盗编号为5。编号为5的海盗会提出什么分配方案呢？如果从游戏的开头出发进行分析，那是走不了多远的。其原因在于，所有的战略决策都是要确定：“如果我这样做，那么下一个人会怎样做？”因此在你以下海盗所做的决定对你来说是重要的，
3、而在你之前的海盗所做的决定并不重要，因为你反正对这些决定也无能为力了。最厉害的5号海盗需要知道其他4名海盗是怎么想的.好难猜！对4号海盗来说，如果5号海盗被扔进海里喂鲨鱼了，他只需要猜透其余3名海盗的算盘。对3号海盗而言，他只须猜透1号和2号海盗 对2号海盗而言，他只须猜透1号海盗 那我们就倒过来，由易到难 我们的出发点应当是游戏进行到只剩两名海盗即1号和2号的时候。这时最厉害的海盗是2号，而他的最佳分配方案是一目了然的：100块金子全归他一人所有，1号海盗什么也得不到。3号海盗的分配方案：3号海盗分得99块金子，2号海盗一无所获，1号海盗得1块金子。1号海盗知道，如果3号的方案被否决，那么最
4、后将只剩2个海盗，而1号将肯定一无所获此外，3号也明白1号了解这一形势。因此，只要3号的分配方案给1号一点甜头使他不至于空手而归，那么不论3号提出什么样的分配方案，1号都将投赞成票。因此3号需要分出尽可能少的一点金子来贿赂1号海盗 4号的分配方案应是：99块金子归自己，3号一块也得不到，2号得1块金子，1号也是一块也得不到。4号海盗的策略也差不多。他需要有50%的支持票，因此同3号一样也需再找一人做同党。他可以给同党的最低贿赂是1块金子，而他可以用这块金子来收买2号海盗。因为如果4号被否决而3号得以通过，则2号将一文不名。5号海盗的分配方案应该是：98块金子归自己，1块金子给3号，1块金子给1
5、号。5号海盗的策略稍有不同。他需要收买另两名海盗，因此至少得用2块金子来贿赂，才能使自己的方案得到采纳。讨论：为什么贿赂1号和3号而不是4号和2号？总结 分析所有这类策略游戏的奥妙就在于应当从结尾出发倒推回去。游戏结束时，你容易知道何种决策有利而何种决策不利。在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策问题。多阶段决策问题7E52D1D23738C1C2C3B1B2 A755586757 下图表
6、示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。试用动态规划的最优化原理求出A-E的最省费用。2 最短距离问题最短距离问题 如图从A到E共分为4个阶段，即第一阶段从A到B，第二阶段从B到C，第三阶段从C到D，第四阶段从D到E。除起点A和终点E外，其它各点既是上一阶段的终点又是下一阶段的起点。例如从A到B的第一阶段中，A为起点，终点有B1，B2两个，因而这时走的路线有两个选择，一是走到B1，一是走到B2。若选择B2的决策，B2就是第一阶段在我们决策之下的结果，它既是第一阶段路线的终点，又是第二阶段路线的始点。在第二阶段，再从B2点出发，对于B2点就有一个可供选择的终点集合(C1，C
7、2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就同理递推下去，可看到各个阶段的决策不同，线路就不同。不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长短。故此问题的要求是：在各个阶段选取一个恰当的决策恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解决这个问题呢？要求在各阶段选取一个恰当的决策要求在各阶段选取一个恰当的决策 用枚举法用枚举法把所有由把所有由A-E可能的每一条路线的距可能的每一条路线的距离算出来，然后互相比较，找出最短离算
8、出来，然后互相比较，找出最短者，相应地得出了最短路线。者，相应地得出了最短路线。用动态规划法求解用动态规划法求解决策过程：决策过程：（1）由目标状态）由目标状态E向前推，可以分成四个阶向前推，可以分成四个阶段，即四个子问题。段，即四个子问题。DE CE BE AE（2）策略：每个阶段到）策略：每个阶段到E的最省费用为本阶的最省费用为本阶段的决策路径。段的决策路径。（3）D1，D2是第一次输入的结点。他们到E都只有一种费用：f(D1)=5 f(D2)=2 E52D1D2目前无法定下，哪一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算（4）C1，C2，C3是第二次输入结点，他
9、们到D1，D2各有两种费用。此时应计算C1，C2，C3分别到E的最少费用。f(C1)=minC1D1+f(D1)，C1D2+f(D2)。计算结果是f(C1)=C1D1+f(D1)=8 （D1)同理C2的决策路径计算结果是C2+D2+E,f(C2)=7 。同理C3的决策路径计算结果是C3+D2+E，f(C3)=10。E8752D1D23738C1C2C35710此时也无法定下第一，二阶段的城市那二个将在整体的最此时也无法定下第一，二阶段的城市那二个将在整体的最优决策路径上。优决策路径上。（5）第三次输入结点为B1，B2，而决策输出结点可能为C1，C2，C3。仿前计算可得Bl，B2的决策路径为如下
10、情况。Bl:B1C1 费用 f(B1)=5+8=13，B2:B2C1 费用 f(B2)=6+8=14，75B1B25867E8752D1D23738C1C2C357101314 此时也无法定下第一，二，三阶段的城市那此时也无法定下第一，二，三阶段的城市那三个将在整体的最优决策路径上。三个将在整体的最优决策路径上。（6）第四次输入结点为A，决策输出结点可能为B1，B2。同理可得决策路径为A：AB2，费用5+14=19此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去决定。75B1B2586
11、7E8752D1D23738C1C2C357101314A1975如何用计算机实现上述算法？用数组来存储中间结果，用空间代价换取时间效率 先自底向上构造中间结果，再自顶向下作出最优决策ABCDEf(A)f(B1)f(C1)f(D1)0f(B2)f(C2)f(D2)f(C3)ABCDE1913850147210ABCDEB2C1D1EC1D2ED2由表二和表三作出最优决由表二和表三作出最优决策：策：AB2C1D1E表一：表二：各城市到E的最短距离表三：各城市的最优后继（使其到E 最近）小结及比较与穷举法相比，动态规划的方法有两个明显的优点:(1)大大减少了计算量(2)丰富了计算结果 从上例的求解
12、结果中，我们不仅得到由A点出发到终点E的最短路线及最短距离，而且还得到了从所有各中间点到终点的最短路线及最短距离，这对许多实际问题来讲是很有用的。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题3.动态规划总体思想动态规划总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用递归法求解时，有些子问题被重复计算了许多次。nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)
13、T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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)是先把问题分成多个子问题（一般地每个子问题是互相关联和影响的），再依次研究逐个问题的决策。决策就是某个阶段的状态确定后，从该状态演变到下一阶段状态的选择。当全体子问题都解决时，整体问题也随之解决。最优子结构性质最优子结构性质 子问题重叠性质子问题重叠性质
14、 动态规划的解题思路最优子结构性质最优子结构性质 一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。子问题的重叠性子问题的重叠性 动态规划的关键在于解决冗余解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。选择动态规划算法
15、是因为动态规划算法在空间上可以承受，而搜索算法在时间上却无法承受，所以我们舍空间而取时间。找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。思考与练习 若城市路径示意图如下图所示，图中，每条边上的数字是通过这段道路所须的平均时间。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地所需时间最短路径和总时间。4、数塔问题、数塔问题 有形如下图所示的数塔，从顶部出发，在每一结点可有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路以选择向左走或是向右走，一直走到底层，要求
16、找出一条路径，使路径上的值最大。径，使路径上的值最大。用用暴力暴力的方法，可以吗？的方法，可以吗？这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230=10243 109=10亿）。试想一下：试想一下：拒绝拒绝暴力，暴力，倡导倡导和谐和谐从顶点出发时到底向左走还是向右走从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。上的最大值求出来了才能作出决策。可见，由下层的子问题可以得到上层
17、可见，由下层的子问题可以得到上层的子问题，所以，可从底层开始，层层的子问题，所以，可从底层开始，层层递进，最后得到最大值。递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：5 海盗盗宝问题 海盗有一背包，能容纳10公斤物品，现有三件宝物：重量分别是6，5，5公斤,价值分别是30万，20万，15万 请给出装载方案，使背包价值达到最大。给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?目标：使装入背包中物品的总价值最大约束条件：装入的物品总重不得超过
18、C海盗盗宝问题 海盗有一背包，最大容积为9，现有5件宝物：体积si分别是2、3、4、5和4公斤 价值vi分别是3、7、5、9和 8 请给出装载方案，使背包价值达到最大。S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8C=9一开始，见物品就装，物品1、2、3全装入，背包装满了，得到背包总价值为15，这是不是最大价值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考虑只有前三个物品的情况考虑只有前三个物品的情况物品物品4该不该装？有两个选择：该不该装？有两个选择：（1）不装，背包价值不变，为）不装，背包价值不变，为15S1=2v1
19、=3S2=3v2=7S3=4v3=5S4=5v4=9（2）装入，它占去的体积为装入，它占去的体积为5，得到价值为，得到价值为9，剩剩下容积下容积4最多可以装下多大价值？最多可以装下多大价值？考虑只有前考虑只有前4个个物品的情况物品的情况这是一个这是一个n=3(从前三个物品中选择），容量从前三个物品中选择），容量c=4的子问题。的子问题。目前最优：装入物品目前最优：装入物品2和物品和物品4，总价值为，总价值为16若已知这个子问题的解是：若已知这个子问题的解是：装物品装物品2，得价值为，得价值为7。S1=2v1=3S3=4v3=5S4=5v4=9（2）装入物品装入物品4，它占去的体积为，它占去的体
20、积为5，得到价值为，得到价值为9，剩下容积剩下容积4最多可以装下多大价值？最多可以装下多大价值？S2=3v2=7S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考虑考虑5个物品的情况个物品的情况S2=3v2=7物品物品5该不该装？该不该装？(1)不装，得到背包价值仍为不装，得到背包价值仍为16（2）若装入物品）若装入物品5，占用体积为，占用体积为4，得价值为，得价值为8，背包剩余容，背包剩余容积为积为5。如何在前如何在前4个物品中选择装入，使背包价值最大化？个物品中选择装入，使背包价值最大化？这是这是n=4,c=5的一个子问题。的一个子问题。若得到该子问题的解为：若得到该子问题
21、的解为：装入物品装入物品1、2，得价值为，得价值为10S1=2v1=3S3=4v3=5S5=4v5=8考虑考虑5个物品的情况个物品的情况S2=3v2=7目前最优：装入物品目前最优：装入物品5和和1、2，总价值为，总价值为1816S4=5v4=9子问题的构造 当n=1时:只有一个物品，s1=2,v1=3 若背包容量c=0、1，则无法装入物品1，得到背包价值为0若背包容量c=2、3、4、5、6，7，8，9则可装入物品1，得到背包价值为3。C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3考虑两个物品的情况 当n=2时，有两个物品，
22、s1=2,v1=3，s2=3,v2=7 若背包容量c=0、1，得到背包价值为0若背包容量c=2，可装入物品1，得总价值m22=3若背包容量c=3，m23=7若背包容量c=4,m24=7若背包容量c=5,m25=10若不装物品2，m23=m13=3若装入物品2，m23=v2+m13-3=7+0=7m26=10 m27=10 m28=10 m29=10 若不装物品2，m25=m15=3若装入物品2，m25=v2+m15-3=7+3=7递推关系的建立 用mij来表示从前i个物品中选取物品装入容量为j的背包所得的最大价值。则要寻求的是mnc。mij是以下两个值的最大值（1）mi-1j:即不装入物品i,
23、背包价值与仅考虑前i-1个物品时情况相同；（2）vi+mi-1j-si:即装入物品i,再从前i-1个物品中选取，使背包剩余容积j-si价值最大化。构造价值数组S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001020304050背包容量j从前i个物品中选取S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121540037710101216165018背包容量j从前i个物品中
24、选取构造最优解012345678900000000000100333333332003771010101010300377101012121540037710101216165003781011151618因m59m49,物品5被装入，剩余c=9-s5=5因m45m35,物品4被装入，剩余c=9-s4=0 void Knapsack(int t v,int w,int c,int n,float mN)/构造价值数组m int i,j;for(i=0;i=n;i+)mi0=0;for(j=0;j=c;j+)m0j=0;for(i=1;n;i+)/计算前计算前n-1行行 for(j=1;jwi;j+)mij=mi-1j;for(j=wi;j mi-1j)mij=t;else mij=mi-1j;/计算最后一行的mnct=vn+mn-1c-wn;If(t mn-1c)mnc=telse mnc=mn-1c;void Trackback(int mN,int w,int c,int n,int x)int i,j;for(i=n;i0;i-)if(mic=mi-1c)xi=0 else xi=1;c=c-wi;上机作业 编程求解数塔问题 编程求解0-1背包问题
