C语言----动态规划.ppt

第十章 动态规划用递推代替递归用递推代替递归用空间换时间用空间换时间5/9/20241.10.1 什么是动态规划1、最短路径问题2、数塔问题5/9/20242.7E52D1D23738C1C2C3B1B2 A755586757 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。试用动态规划的最优化原理求出A-E的最省费用。1 最短距离问题5/9/20243.如图从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，C2，C3)；若选择由B2走至C2为第二阶段的决策，则C2就是第二阶段的终点，同时又是第三阶段的始点。同理递推下去，可看到各个阶段的决策不同，线路就同理递推下去，可看到各个阶段的决策不同，线路就不同。不同。5/9/20244.很明显，当某阶段的起点给定时，它直接很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长影响着后面各阶段的行进路线和整个路线的长短。短。故此问题的要求是：在各个阶段选取一个故此问题的要求是：在各个阶段选取一个恰当的决策，使由这些决策组成的一个决策序恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总路程最短。如何解列所决定的一条路线，其总路程最短。如何解决这个问题呢？决这个问题呢？要求在各阶段选取一个恰当的决策要求在各阶段选取一个恰当的决策5/9/20245.决策过程：决策过程：（1）由目标状态）由目标状态E向前推，可以分成四个阶向前推，可以分成四个阶段，即四个子问题。段，即四个子问题。DE CE BE AE（2）策略：每个阶段到）策略：每个阶段到E的最省费用为本阶的最省费用为本阶段的决策路径。段的决策路径。用动态规划法求解用动态规划法求解5/9/20246.（3 3）D1D1，D2D2是第一次输入的结点。他们到是第一次输入的结点。他们到是第一次输入的结点。他们到是第一次输入的结点。他们到E E都只有一种费用：都只有一种费用：都只有一种费用：都只有一种费用：f(D1)=5 f(D2)=2 f(D1)=5 f(D2)=2 E52D1D2目前无法定下，哪一个点将在全程最优策略的路径上。第二阶段计算中，5，2都应分别参加计算5/9/20247.（4 4）C1C1，C2C2，C3C3是第二次输入结点，他们到是第二次输入结点，他们到是第二次输入结点，他们到是第二次输入结点，他们到D1D1，D2D2各有两种费用。此时应计算各有两种费用。此时应计算各有两种费用。此时应计算各有两种费用。此时应计算C1C1，C2C2，C3C3分别分别分别分别到到到到E E的最少费用。的最少费用。的最少费用。的最少费用。f(C1)=minC1D1+f(D1)f(C1)=minC1D1+f(D1)，C1D2+C1D2+f(D2)f(D2)。计算结果是计算结果是计算结果是计算结果是f(C1)=C1D1+f(D1)=8 f(C1)=C1D1+f(D1)=8 （D1)D1)同理同理同理同理C2C2的决策路径计算结果是的决策路径计算结果是的决策路径计算结果是的决策路径计算结果是C2+D2+E,C2+D2+E,f(C2)=7 f(C2)=7 。同理同理同理同理C3C3的决策路径计算结果是的决策路径计算结果是的决策路径计算结果是的决策路径计算结果是C3+D2+EC3+D2+E，f(C3)=10f(C3)=10。E8752D1D23738C1C2C357105/9/20248.（5 5）第三次输入结点为）第三次输入结点为）第三次输入结点为）第三次输入结点为B1B1，B2B2，而决策输出结，而决策输出结，而决策输出结，而决策输出结点可能为点可能为点可能为点可能为C1C1，C2C2，C3C3。仿前计算可得。仿前计算可得。仿前计算可得。仿前计算可得BlBl，B2B2的的的的决策路径为如下情况。决策路径为如下情况。决策路径为如下情况。决策路径为如下情况。Bl:B1C1 Bl:B1C1 费用费用费用费用 f(B1)=5+8=13 f(B1)=5+8=13，B2:B2C1 B2:B2C1 费用费用费用费用 f(B2)=6+8=14 f(B2)=6+8=14，75B1B25867E8752D1D23738C1C2C3571013145/9/20249.（6 6）第四次输入结点为）第四次输入结点为）第四次输入结点为）第四次输入结点为AA，决策输出结点可能为，决策输出结点可能为，决策输出结点可能为，决策输出结点可能为B1B1，B2B2。同理可得决策路径为同理可得决策路径为同理可得决策路径为同理可得决策路径为AA：AB2AB2，费用，费用，费用，费用5+14=195+14=19此时才正式确定每个子问题的结点中，那一个结点将此时才正式确定每个子问题的结点中，那一个结点将此时才正式确定每个子问题的结点中，那一个结点将此时才正式确定每个子问题的结点中，那一个结点将在最优费用的路径上。在最优费用的路径上。在最优费用的路径上。在最优费用的路径上。子问题的决策中，只对同一城市（结点）比较优劣。子问题的决策中，只对同一城市（结点）比较优劣。子问题的决策中，只对同一城市（结点）比较优劣。子问题的决策中，只对同一城市（结点）比较优劣。而同一阶段的城市（结点）的优劣要由下一个阶段去而同一阶段的城市（结点）的优劣要由下一个阶段去而同一阶段的城市（结点）的优劣要由下一个阶段去而同一阶段的城市（结点）的优劣要由下一个阶段去决定。决定。决定。决定。75B1B25867E8752D1D23738C1C2C357101314A19755/9/202410.2、数塔问题、数塔问题 有形如下图所示的数塔，从顶部出发，在每有形如下图所示的数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的值最大。层，要求找出一条路径，使路径上的值最大。5/9/202411.用用暴力暴力的方法，可以吗？的方法，可以吗？5/9/202412.这道题如果用枚举法（暴力思想），在数塔层数稍大的情况下（如31），则需要列举出的路径条数将是一个非常庞大的数目（230=10243 109=10亿）。试想一下：试想一下：5/9/202413.拒绝拒绝暴力，暴力，倡导倡导和谐和谐5/9/202414.从顶点出发时到底向左走还是向右走从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从应取决于是从左走能取到最大值还是从右走能取到最大值，只要左右两道路径右走能取到最大值，只要左右两道路径上的最大值求出来了才能作出决策。上的最大值求出来了才能作出决策。可见，由下层的子问题可以得到上层可见，由下层的子问题可以得到上层的子问题，所以，可从底层开始，层层的子问题，所以，可从底层开始，层层递进，最后得到最大值。递进，最后得到最大值。结论：自顶向下的分析，自底向上的计算。结论：自顶向下的分析，自底向上的计算。考虑一下：考虑一下：5/9/202415.如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。10.2 动态规划的基本思想动态规划的基本思想 5/9/202416.动态规划的基本步骤动态规划的基本步骤 动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值（最大值或最小值）的那个解。设计一个动态规划算法，通常可以按以下几个步骤进行：5/9/202417.（1）找出最优解的性质，并刻画其结构特征。）找出最优解的性质，并刻画其结构特征。（2）递归地定义最优值。）递归地定义最优值。（3）以）以自底向上自底向上的方式计算出最优值。的方式计算出最优值。（4）根据计算最优值时得到的信息，构造一个最优解。）根据计算最优值时得到的信息，构造一个最优解。其中（其中（1）（）（3）步是动态规划算法的基本步骤。）步是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤（在只需要求出最优值的情形，步骤（4）可以省去。）可以省去。若需要求出问题的一个最优解，则必须执行步骤若需要求出问题的一个最优解，则必须执行步骤（4）。此时，在步骤（）。此时，在步骤（3）中计算最优值时，通常）中计算最优值时，通常需记录更多的信息，以便在步骤（需记录更多的信息，以便在步骤（4）中，根据所记）中，根据所记录的信息，快速构造出一个最优解。录的信息，快速构造出一个最优解。基本步骤基本步骤 5/9/202418.动态规划问题的特征动态规划问题的特征 动态规划算法的有效性依赖于问题本身所具有的两个重要性质：1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。5/9/202419.10.3 最长有序子序列最长有序子序列I012345678NumI1472583695/9/202420.子问题的构造子问题“求以ak（k=1,2,3N）为终点的最长上升子序列的长度”虽然这个子问题和原问题形式上并不完全一样，但是只要这N 个子问题都解决了，那么这N 个子问题的解中，最大的那个就是整个问题的解。该子问题可以递推求解5/9/202421.假定MaxLen(k)表示以ak 做为“终点”的最长上升子序列的长度，那么：MaxLen(1)=1MaxLen(k)=Max MaxLen(i)：1i k 且 ai=cij-1 cij=ci-1j;否则 cij=cij-1;LCS(Xm,Yn)=LCS(Xm,Yn)+xm5/9/202438.0000000000000例：X=A B C B D A B Y=B D C A B A 0 B D C A B A0ABCBDABAABABCABCBABCBDABCBDAABCBDAB B BD BDC 5/9/202439.0000000000111011112201122220112233012223301223340122344例：X=A B C B D A B Y=B D C A B A0 B D C A B A0ABCBDAB5/9/202440.void LCS(int m，int n，char*x，char*y,char*z,int*c)/不用数组b，构造最优解的非递归算法 int i=m,j=n;int k=cmn;/最长公共子序列的长度 while(i0&j0)if(xi=yj)zk-=xi;i-;j-;else if(ci-1j=cij-1)i-;else j-;构造最长公共子序列构造最长公共子序列5/9/202441.10.5 0-1背包问题 给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?目标：使装入背包中物品的总价值最大约束条件：装入的物品总重不得超过C5/9/202442.海盗盗宝问题海盗盗宝问题 海盗有一背包，最大容积为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=95/9/202443.一开始，见物品就装，物品1、2、3全装入，背包装满了，得到背包总价值为15，这是不是最大价值呢？S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8考虑只有前三个物品的情况考虑只有前三个物品的情况5/9/202444.物品物品4该不该装？有两个选择：该不该装？有两个选择：（1）不装，背包价值不变，为）不装，背包价值不变，为15S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9（2）装入，它占去的体积为装入，它占去的体积为5，得到价值为，得到价值为9，剩剩下容积下容积4最多可以装下多大价值？最多可以装下多大价值？考虑只有前考虑只有前4个个物品的情况物品的情况5/9/202445.这是一个这是一个n=3(从前三个物品中选择），容量从前三个物品中选择），容量c=4的子问题。的子问题。目前最优：装入物品目前最优：装入物品2和物品和物品4，总价值为，总价值为16若已知这个子问题的解是：若已知这个子问题的解是：装物品装物品2，得价值为，得价值为7。S1=2v1=3S3=4v3=5S4=5v4=9（2）装入物品装入物品4，它占去的体积为，它占去的体积为5，得到价值为，得到价值为9，剩下容积剩下容积4最多可以装下多大价值？最多可以装下多大价值？S2=3v2=75/9/202446.S1=2v1=3S3=4v3=5S4=5v4=9S5=4v5=8考虑考虑5个物品的情况个物品的情况S2=3v2=7物品物品5该不该装？该不该装？(1)不装，得到背包价值仍为不装，得到背包价值仍为165/9/202447.（2）若装入物品）若装入物品5，占用体积为，占用体积为4，得价值为，得价值为8，背包剩余容，背包剩余容积为积为5。如何在前如何在前4个物品中选择装入，使背包价值最大化？个物品中选择装入，使背包价值最大化？这是这是n=4,c=5的一个子问题。的一个子问题。若得到该子问题的解为：若得到该子问题的解为：装入物品装入物品1、2，得价值为，得价值为10S1=2v1=3S3=4v3=5S5=4v5=8考虑考虑5个物品的情况个物品的情况S2=3v2=7目前最优：装入物品目前最优：装入物品5和和1、2，总价值为，总价值为1816S4=5v4=95/9/202448.子问题的构造当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=35/9/202449.考虑两个物品的情况当n=2时，有两个物品，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=75/9/202450.递推关系的建立用mij来表示从前i个物品中选取物品装入容量为j的背包所得的最大价值。则要寻求的是mnc。mij是以下两个值的最大值（1）mi-1j:即不装入物品i,背包价值与仅考虑前i-1个物品时情况相同；（2）vi+mi-1j-si:即装入物品i,再从前i-1个物品中选取，使背包剩余容积j-si价值最大化。5/9/202451.构造价值数组S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001020304050背包容量j从前i个物品中选取5/9/202452.S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001003333333320037710 10 10 101030037710 10 12 121540037710 10 12 16165018背包容量j从前i个物品中选取5/9/202453.构造最优解0123456789000000000001003333333320037710 10 10 10 1030037710 10 12 12 1540037710 10 12 16 1650037810 11 15 16 18因m59m49,物品5被装入，剩余c=9-s5=5因m45m35,物品4被装入，剩余c=9-s4=05/9/202454.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;5/9/202455./计算最后一行的mnct=vn+mn-1c-wn;If(t mn-1c)mnc=telse mnc=mn-1c;5/9/202456.思考：思考：免费馅饼免费馅饼 5/9/202457.如何解决？子问题：最后1秒最多能接住几个，最后两秒、最后两秒.还与当时他站的位置有关子问题是二维的：Tij表示第i秒若站在位置j，从第i秒之后能接住多少个馅饼5/9/202458.Tij表示第i秒若站在位置j，从第i秒之后能接住多少个馅饼Tij:若第i+1秒站在位置j，那么第i秒他可能到达的位置是j-1,j,j+1,去那个位置接到馅饼最多？T(i,j-1)Tij=Ti+1j+max T(i,j)T(i,j+1)再考虑一下j=0和j=10的情况即可5/9/202459.计算过程00000000000000111000000000002000000000001000000 0 1 2 3 4 5 6 7 8 9 10012345675/9/202460.00004000000000114330000000003100000000001000000 0 1 2 3 4 5 6 7 8 9 10012345675/9/202461.课后任务：课后任务：一、一、DIYDIY在线作业在线作业(4):(4):20082008ACM ProgrammingACM ProgrammingExerciseExercise（4 4）_ _动态规划动态规划二、常规练习（包含以上作业）二、常规练习（包含以上作业）10031003、1466 1466、10871087、11591159、11761176、10581058、10691069、20592059、20842084、215121515/9/202462.