《[工学]动态规划题》由会员分享，可在线阅读，更多相关《[工学]动态规划题（9页珍藏版）》请在金锄头文库上搜索。
1、动态规划在信息学奥林匹克竞赛中的应用*快餐问题问题描述：Peter 最近在 R 市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套由 A 个汉堡、B 个薯条、C 个饮料组成。价格便宜。为了提高产量，Peter 从麦当劳公司引进了 N 条生产线。所有的生产线都能生产汉堡、薯条、饮料，由于每条生产线能提供的生产时间是有限的，不同的，而生产汉堡、薯条、饮料的单位生产时间不同，这使得 Peter 很为难，不知如何安排生产才能使一天中生产的套餐产量最大。请你编程，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100 个。解：pi,j,k表示前 i 条生产线生产 j
2、 个汉堡、k 个薯条的情况下，最多可生产的饮料个数ri,j,k表示第 i 条生产线生产 j 个汉堡、k 个薯条的情况下，最多可生产的饮料个数状态转移方程：pi,j,k=maxpi-1,j1,k1ri,i-j1,k-k1 其中 j1,k1 的范围：0=0) and (f(k-1)mod 2,i-wk=true) ) then fk mod 2,i:=true else f(k-1)mod 2,i:=false;for i:=0 to V do f(k-1)mod 2,i:=false ;end; i:=V;while(fN mod 2,itrue) do dec(i);writeln;write
3、ln(V-i);end.*叠矩形问题描述有 N 个不同大小的矩形，现要将其中若干个 (或全部) 叠成一条柱。且在所叠成的柱中，任何两个相连的矩形中，上面的矩形的阔度，必定要小于下面的一个矩形。 每一个矩形只可以使用一次，使用时可以自由选择摆放的方向 (即可自由选择哪边是高哪边是阔)。请找出一个叠矩形的方案，使所叠成的柱的高度为最高。 输入输入资料存放在一名为 blocks.in 的文字文件内。档内的第一行有一个正整数 N 。随后有 N 行，每行有两个正整数 a b ，它们代表一个矩形的两个边长。 N 最大为 20，而每边最长为 200。 输出请将答案输出到一名为 blocks.out 的文字文
4、件内。输出的第一行应有两个正整数 H M 。其中 H 代表你找到的最高高度， M 代表一共享了多少个矩形。随后有 M 行，每行有两个正整数 s h ， s 代表所使用的矩形的编号 (第一个输入的矩形编号为 1，第二个为 2，如此类推)。 h 则代表该矩形在叠柱时作为高的那边的边长。矩形的输出要求是你所找到的方案由下而上，最下面的一个先输出。例子：blocks.in32 21 22 3 输出例子blocks.out6 33 21 22 2解法一：*胖子跳舞问题描述：一个胖子很喜欢玩跳舞毯，但是每次都玩的很累。跳舞毯共有 4 个键位，中间，上，下，左，右。上下左右一次为 1，2 ，3，4。游戏开始
5、时，人双脚在中间，一只脚从中间到任一键位耗费体力值 2，从任意键位到相邻键位耗费体力值 3，到相对键位耗费体力值 4。一只脚在原地重复踏一下耗费体力值 1。现在给出一个跳舞序列（由 1，2，3，4 组成）请计算出用最优步骤跳舞，使耗费体力最少。很明显，跳舞序列是固定，可以按这个序列定义动态规划的阶段。阶段：设 f(i)表示前 i 个序列跳舞所需最小消耗，规定 f(0)=0。状态：人的两只脚的位置就表示两种状态，即每一阶段有两种状态用 si1,si2，如第 0 阶段的状态 s01=0,s02=0。决策：第 i+1 阶段的状态可以只能由 si1,si2，变换得到。即对跳舞序列的第 i+1 个，可以
6、动左或右脚去实现。状态转移：f(i)=mins i-11到 ai 的消耗，s i-12到 ai 的消耗)+f(i-1) ，a i表示跳舞的第 i 个序列。*砝码称重问题描述：有一组砝码，重量互不相等，分别为 m1、m 2、m 3mn；它们可取的最大数量分别为 x1、x 2、x 3xn。现要用这些砝码去称物体的重量,问能称出多少种不同的重量。输入：第一行一个整数 n（n=0,（0i最大重，0kx i）*城市交通 双重动态设计某城市有 n(1n50)个街区，某些街区有公共汽车线路相连，如下图，图中边上的数字为两个街区间汽车的旅行时间（也就是乘客等车时间）。从 1 到 5 的最短路线为 1-3-5
7、用时 44 分钟。此主题相关图片如下：现市政府要改善交通，决定加开 m(1m10)条线路的公共汽车，并规定：只有已有了公共汽车线路的才能加开线路，加开一条线路后，等车时间减半，若再加开一条，等车时间再减半，依此类推。如加开两条线路，1 到 5 的时间最短是 22 分钟，加开线路是 1-3，3-5 。求加开哪些线路，可使街区 1 到 n 的时间最短，并输出出加开的线路。 参考 FLOYD 算法。以加开的公交线路数为阶段。阶段：第 0 阶段就是不加开任何线路的情况，即原始状态（直接用算法就可求出任何两点的最短旅行时间）。第 1 阶段就是只加开一条线路的情况，依此类推。第 m 阶段就是加开了 m 条
8、线路的情况也就是所求。状态：在每一阶段，任何两个街区加开 g(1gm)条线路的后的最短旅行时间，即共 n*n 个状态。决策：在道路 a-b 上增加 g 条线路可分为以下两个问题（如果 k 是最短路上的一点）在 a-k 的道路上增加 t 条边在 k-b 的道路上增加 g-t 条边k 可取 0 到 m 间的任何整数。问题“在道路 a-b 上增加 m 条线路”的最优解取决于以上两个问题的最优组合。即：“ 在 a-k 的道路上增加 t 条边”后旅行时间和“在 k-b 的道路上增加 m-t 条边”后旅行时间之和最小值。状态移方程：可参考以上的分析。综合，以上分析可以发现：上述的动态规划，第一个层次是以“
9、加开的公交线路数为阶段”，进行动态规划，比如要完成加条公交线路的任务，就要先要完成加条和加条线路的问题。而第二层次是以“允许 k 为中间结点”(0=p=0）。过程详解：设 map 为邻接表，邻接表中的 0 表示没有通路。如 mapi,j=0 表示 i,j 间没有通路。val0.10是有 10 个 map 单元的数组，val0存储为不加开任何线路任何两结点的最短旅行时间，valp存储加开 p 条线路任何两结点的最短旅行时间。way0.10,1.50,1.50,1.2记录 i 到 j 路径上新增 p 条线路的最佳方案，其中 wayp,i,j,2存储 i-j 的路径的中间结点 k，wayp,i,j,
10、1存 i-k 的路径上新增的线路数。对 val0运用算法，即可求出不加开线路，任何两结点的最短旅行时间。求 val1（只加开一条线路）val1=邻接表（注意，邻接表中的 0 表示没有通路）； val1中各值减半；for k=1 to n do列举各个中间结点for i=1 to n dofor j=1 to n do列举所有的两街区线路if(i 到 k 有通路 andj 到 k 有通路 andij) thenbegin for(列举 q 的所有可能 )if(Valpi,j=0 or Valpi,jValqi,kVal1-qk,j)then记录较优值；end;最后的结果就是：val1i,j=i
11、到 k 的通路新增 q 条线路的最短时间k 到 j 的通路新增 1-q 条线路的最短时间 中最优值；*方格取数 多进程的动态规划问题描述：设有 n*n 的方格图（n=x=1)状态：每个阶段有若干个状态，如上所述阶段 k 的状态有: (x,k+1-x),(k=x=1)。决策：在每个位置有可能有两个或一个决策可选择，即向下或向右走（当然不能出界）。状态转移方程：位置(x,y)的状态：S(x,y)=min s(x-1,y), s(x,y-1) +格子(x,y)中的数。现考虑走两次。题目中是两次分开走的，但我们可以看成两个人同时走。这时依然按照行走的步数来分类。这样的情况下有一个不同的情况是：可能两个
12、人同时走入同一个格子取数，这时肯定不能取两次数。两条路线同时进行的动态规划中，状态和决策以及状态转方程移要复杂一些。两条路线同时进行的动态规划阶段：按所走的步数来分阶段，从左上角走到右下角，共 2n-1 个步骤，故共 2n-1 个阶段。但，有两条线路，故每一阶段的状态都会复杂一些。状态：有两线路同时走，在某阶段的某状态，要用两个坐标来分别表示两线路的两个点。如：第一阶段，共一个状态：(1,1),(1,1)；第二阶段，(1,2),(1,2);(1,2),(2,1);(2,1),(1,2);(2,1),(2,1) 共四个状态。由于在第 k 阶段的任何两个点的 x,y 坐标是有关系的：k+1=x+y
13、 。故可只用坐标来表示一点的坐标，故状态可表示为(x1,x2)，对应的 y 坐标为：y1=k+1-x1,y2=k+1-x2。决策：若用 0,1 分别表示向下或向右走，则每个状态的可能决策有四种：(1,1),(0,0),(1,0),(0,1)。两个数值分别表示两个点的下一步走向。状态转移方程：设 map(x,y)为方格图，f(k,x1,x2)表示第 k 个阶段走到(x1,x2)状态的最大和f(0,1,1)map(x1,1+1-x1)即 map(1,1)f(k,x1,x2)=maxf(k-1,x1,x2)+map(x1,y1)x1=x2，f(k-1,x1,x2)+map(x1,y1)map(x2,
14、y2) x1x2(x1,x2)表示可通过某决策到达(x1,x2) 的所有点 *资源分配问题问题描述：设有资源 a 分配给 n 个项目，g r(x)为将数量为 x 的资源分配给项目 i 所能得到的利润，i=1,2,3,n。最合理的资源分配导致解下面的问题： maxZ=g1(x1)+g2(x2)+gn(xn)其中： x1+x2+xn=a，x i=0解：设 fk(n)为资源 n 分配给前 k 个项目所得的最大利润，则 fk(n)=maxgk(x)+fk-2(a-x) 其中 0=x=a本题设计动态规划时，以项目为纵（阶段），以资源为横。如，第一阶段，就是求出前一个项目在获得所有不同资源情况下的最大利润，例如f1(0)、f 1(1)分别表示第一阶段，在获得资源为 0、1 时所取得的最大利润；第二阶段，就是求出前二个项目在获得所有不同资源情况下的最大利润，例
