2022年动态规划算法 .pdf

《2022年动态规划算法 .pdf》由会员分享，可在线阅读，更多相关《2022年动态规划算法 .pdf（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、动态规划（一）、动态规划的基本思想：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问

2、题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。二、设计动态规划法的步骤：1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。步骤 1-3 是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4 可以省略，步骤3 中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤 3 中记录的信息必须足够多以便构造最优解。三、动态规划问题的特征：动态规划算法的有效性依赖

3、于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。（二）、动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行：1.划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就

4、无法用动态规划求解。2.选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。3.确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。4.写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。动态规划的主要难点在于理论上的设计，一旦设计完

5、成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：标准动态规划的基本框架frame 1. 对 fn+1(xn+1) 初始化 ; 边界条件 2. for k:=n downto 1 do 3. for 每一个 xk? Xk do 4. for 每一个 uk? Uk(xk) do begin 5. fk(xk):= 一个极值 ; 或 6. xk+1:=Tk(xk,uk); 状态转移方程 7. t:=(fk+1(xk+1),vk(xk,uk); 基本方程 (9) 式 8. if t比 fk(xk) 更优 then fk(xk):

6、=t; 计算 fk(xk) 的最优值 end; 9. t:=一个极值 ; 或 10. for 每一个 x1? X1 do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 27 页 - - - - - - - - - 11. if f1(x1) 比 t 更优 then t:=f1(x1); 按照 10 式求出最优指标 12. 输出 t; 但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：1.分析最优解的性质，并刻划其结构特征。2.递归地定义最优

7、值。3.以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。4.根据计算最优值时得到的信息，构造一个最优解。步骤 (1)-(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4) 可以省略，若需要求出问题的一个最优解，则必须执行步骤(4) 。此时，在步骤 (3) 中计算最优值时，通常需记录更多的信息，以便在步骤 (4) 中，根据所记录的信息，快速地构造出一个最优解。 （三）、动态规划概述1. 基本思想：将问题分解为若干小问题，解子问题，然后从子问题得到原问题的解。2. 特点：将问题分解为子问题，这些子问题往往不相互独立。（如果可以用分治法求解，分解的子问题太多，因此，用

8、分治法时间代价太高，消耗指数时间）3. 且某些子问题可能被重复多次计算，因此将计算过的子问题的结果保存。一般，放入表中。4. 应用：往往求解具有某种最优性质的问题，此类问题往往具有多个解，我们要找到具有最优值的那个解。5. 步骤：找出最优解的性质，刻画其特征；递归地定义最优值；以自底向上的方式计算出最优值；根据计算最优值时得到的信息，构造一个最优解。（四）、动态规划问题中的术语阶段：把所给求解问题的过程恰当地分成若干个相互联系的阶段，以便于求解，过程不同，阶段数就可能不同描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k 表示。此外，也有阶段变量是连续的情形。如果过程可以在任何时

9、刻作出决策，且在任意两个不同的时刻之间允许有无穷多个决策时，阶段变量就是连续的。在前面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点 B ，第三个阶段是点B到点 C，而第四个阶段是点C到点 D。状态：状态表示每个阶段开始面临的自然状况或客观条件，它不以人们的主观意志为转移，也称为不可控因素。在上面的例子中状态就是某阶段的出发位置，它既是该阶段某路的起点，同时又是前一阶段某支路的终点。在前面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和 B2，第三个阶段是三个状态 C1，C2和 C3，而第四个阶段又是一个状态D 。过程的状态通常可以用一个或一组数来描述，称为状态变量。一

10、般，状态是离散的，但有时为了方便也将状态取成连续的。当然，在现实生活中，由于变量形式的限制，所有的状态都是离散的，但从分析的观点，有时将状态作为连续的处理将会有很大的好处。此外，状态可以有多个分量( 多维情形 ) ，因而用向量来代表；而且在每个阶段的状态维数可以不同。当过程按所有可能不同的方式发展时，过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。无后效性：我们要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中

11、每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 27 页 - - - - - - - - - 响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。决策：一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。在最优控制中，也称为控制。在许多间题中，决策可以自然

12、而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。决策变量的范围称为允许决策集合。策略：由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。给定 k 阶段状态变量x(k) 的值后，如果这一阶段的决策变量一经确定，第k+1 阶段的状态变量x(k+1) 也就完全确定，即x(k+1) 的值随 x(k) 和第 k 阶段的决策 u(k) 的值变化而变化，那么可以把这一关系看

13、成(x(k)，u(k) 与 x(k+1) 确定的对应关系，用x(k+1)=Tk(x(k),u(k)表示。这是从k 阶段到 k+1 阶段的状态转移规律，称为状态转移方程。最优性原理 : 作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。最优性原理 : 实际上是要求问题的最优策略的子策略也是最优。让我们通过对前面的例子再分析来具体说明这一点：从A到 D，我们知道，最短路径是A B1 C2 D ，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：A B1 C2 是 A到 C2的最短路径， B1 C2 D也是 B1到 D

14、的最短路径 , 事实正是如此，因此我们认为这个例子满足最优性原理的要求。（五）、标号法标号法是一种最佳算法，多用于求图的最短路问题。一、标号法的概念：所谓标号，是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划，它采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，因此标号法是一种最佳算法。二、标号法的算法流程：现有一图 G ，求从起点Vs 到终点 Ve的最短距离。设：Sum(j) 顶点Vj 的标号，代表的是Vs 到 Vj 的最短距离。 Vj?已标味着 Vs 到 Vj 的最短路以及这条路径的长度已求出。M(i,j)Vi到 Vj 的非负长度。H(j) 顶点Vj 的前趋结点。标号法

15、的算法流程如下： sum（s）0 Vs进入队列 L -移出队列L 的队首 Vk - | | | Vk是不是 Ve-|-计算结束打印路径 | N Y | | | | 由 Vk 扩展出结点Vj | | （Vk 与 Vj 之间相连） | | SjSum(k)+M(k， j) | | | | Sj小于 Sum （j ） | | | | | Y | N | | | - | | | | Sum（j ）Sj | H（j ） Vk 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 27 页

16、 - - - - - - - - - | Vj加入队列 L 并对队列 L 按 Sum值由小到大排序 | - 注意： 1. 只有两个顶点间的距离为非负时，才可用标号法。 2. 只有队列的首结点是目标结点时，才可停止计算。 ?否则得出的不一定是最优解。三、例题解析： 1.相邻项序列 (GDOI97第四题 ) 问题描述：对于一个 N*N(=100) 的正整数矩阵M ，存在从MA1，?B1 ? 开始到 MA2，B2结束的相邻项序列. 两个项 MI ，J 和 MK，L? 相邻的件是指满足如下情况之一：(1)I=K+-1和 J=L (2)I=K和 J=L+-1 。任务：从文件中输入矩阵M ，再读入K(K=

17、4)组 MA1，B1 和 MA2，B2的值。对于每一组MA1，B1和 MA2，B2，求一相邻项序列，使得相邻项之差的绝对值之和为最小。输入格式： 4 N 1 9 6 12 每行N个数据，共N行 8 7 3 5 5 9 11 11 7 3 2 6 2 K 4 1 1 4 表示 A1,B1 和 A2,B2 的值，共 K行 2 2 3 4 输出格式： 1 17 第一组数据相邻项之差的绝对值之和的最小值是17 7 5 8 7 9 6 12第一组数据的相邻项序列 2 4 7 9 11 11 解析：本题若将相邻的两个数看作是两个顶点，两个数之差的绝对值作为权，则问题转化成求两个顶点的最短路问题。设： Su

18、mI,J 为从起点 Vs 到结点 MI,J的最短距离。 HI,J记录结点 MI,J的前趋结点。 L 为记录待扩展的结点的队列。鉴于数组进行排序时速度较慢，?所以用链表作为记录结点的队列的类型，适于排序。参考程序：Program gdoi974; const fang:array 1.4,1.2 of integer =(-1,0),(0,-1),(1,0),(0,1); 上下左右四个方向 type 定义 POINT类型 , 其中 X,Y 为结点在矩阵中的坐标,NEXT为队列中的后继结点 point=note; note=record x,y:byte; next:point; end; var

19、 sum:Array 1.100,1.100 of integer; m:Array 1.100,1.100 of integer; h:Array 1.100,1.100,1.2 of byte; f1,f2:text; a,b,x1,y1,x2,y2,n,k,zz:integer; procedure print; var a,b,x,y,x3,y3:integer; c:array 1.100 of integer; flag:boolean; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

20、- - - 第 4 页，共 27 页 - - - - - - - - - begin flag:=true; a:=1; ca:=mx2,y2; x:=x2; y:=y2; while flag do begin a:=a+1; x3:=x; y3:=y; x:=hx3,y3,1; y:=hx3,y3,2; ca:=mx,y; if (x=x1) and (y=y1) then flag:=false; end; 求出整条路径，放入数组C 中 writeln (f2,zz, ,sumx2,y2); for b:=a downto 1 do write (f2,cb, ); 打印结果 write

21、ln (f2); end; procedure add(x,y,i:integer;var l:point); var e,f,g:point; a,b,c:integer; flag:boolean; begin new (e); e.x:=x; e.y:=y; if i=0 then l.next:=e 加入队列 else begin f:=l; g:=f.next; flag:=true; for a:=1 to i do begin if sumg.x,g.ysumx,y then begin e.next:=g; f.next:=e; flag:=false; a:=i; 加入队列

22、end; f:=f.next; g:=f.next; end; if flag then f.next:=e; 加入队列 end; end; procedure try(xz,yz:byte); var a,b,c,sj,x,y,x1,y1:integer; e,l,v:point; flag:boolean; begin fillchar (sum,sizeof (sum),255); 置 Sum值为 -1 sumxz,yz:=0;置起点 Sum值为 0 flag:=true; new (e); e.x:=xz; e.y:=yz; new (l); l.next:=e; 起点进入队列 c:=

23、1; 现在队列结点个数 while flag do begin v:=l.next; dispose (l); 取出首结点V l:=v; c:=c-1;指针下移一位，结点个数减一 x:=v.x; y:=v.y; if (x=x2) and (y=y2) then flag:=false; 若为目标结点，则结束计算 if flag then begin for a:=1 to 4 do 向四个方向扩展 begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 27 页 -

24、 - - - - - - - - x1:=x+fanga,1; y1:=y+fanga,2; if (x10) and (x10) and (y1=n) then begin sj:=sumx,y+abs (mx,y-mx1,y1); if (sj sumx1,y1) or (sumx1,y1=-1) then begin sumx1,y1:=sj; hx1,y1,1:=x; hx1,y1,2:=y;记录路径 add(x1,y1,c,l); 将新扩展出来的结点进入队列 c:=c+1; 结点个数加一 end; end; end; end; end; print;打印结果 end; Begin a

25、ssign (f1,gdoi974.dat); assign (f2,gdoi974.out); reset (f1); rewrite (f2); readln (f1,n); for a:=1 to n do begin for b:=1 to n do read (f1,ma,b); readln (f1); end; 读入数组 readln (f1,k); for a:=1 to k do begin zz:=a; readln (F1,x1,y1,x2,y2); 读入任务 try(x1,y1); end; close(f1); close(f2); End. 四、小结综上所述，标号法

26、是动态规划的一种，它采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，要比一般的搜索优秀得多。它是一种最佳算法。（六）、动态规划教程一. 动态规划含义 : 在现实生活中 , 有一类活动的过程, 由于它的特殊性, 可将过程分成若干个互相联系的阶段, 在它的每一阶段都要做出决策 , 从而使整个过程达到最好的活动效果. 因此 , 各个阶段决策确定后, 组成一个决策序列, 因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程, 就称为多阶段决策过程, 这种问题称为多阶段决策问题. 在多阶段决策问题中, 各个阶段采取的决策, 一般来说是和时间有关的, 决

27、策依赖于当前状态, 又随即引起状态的转移 , 一个决策序列就是在变化的状态中产生出来的, 故有 动态 的含义 ,我们称这种解决多阶段决策最优化的过程为动态规划. 二. 动态规划特征动态规划的显著特征是: 无后效性 , 有边界条件 , 且一般划分为很明显的阶段. 动态规划一般还存在一条或多条状态转移方程. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 27 页 - - - - - - - - - 三. 例题1. Catcher防卫导弹 (GDOI98) 题目讲得很麻烦 ,

28、 归根结底就是求一整串数中的最长不上升序列这道题目一开始我使用回溯算法, 大概可以拿到1/3 的分吧 , 后来发现这其实是动态规划算法中最基础的题目, 用一个二维数组C1.Max,1.2来建立动态规划状态转移方程( 注:C1.Max,1表示当前状态最多可击落的导弹数 ,C1.Max,2表示当前状态的前继标志):Ci=MaxCj+1,(j=i+1.n),然后程序也就不难实现了 . 示范程序 : program catcher_hh; var f:text; i,j,k,max,n,num:integer; a:array 1.4000 of integer; 导弹高度数组 c:array 1.4

29、000,1.2 of integer; 动态规划数组 procedure readfile; begin assign(f,catcher.dat); reset(f); readln(f,num); for i:=1 to num do readln(f,ai); end; procedure work; begin fillchar(c,sizeof(c),0); cnum,1:=1; 清空数组 , 赋初值 开始进行动态规划 for i:=num-1 downto 1 do begin n:=0; max:=1; for j:=i+1 to num do if (aiaj) and (ma

30、xmax then begin max:=ci,1; n:=i; end; 返回寻找路径 repeat writeln(n, ); n:=cn,2; until n=0; end; begin readfile; work; end. 2. Perform巡回演出 (GDKOI2000) 题目描述 : Flute市的 Phlharmoniker乐团 2000 年准备到 Harp 市做一次大型演出, 本着普及古典音乐的目的, 乐团指挥 L.Y.M 准备在到达 Harp 市之前先在周围一些小城市作一段时间的巡回演出, 此后的几天里 , 音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达

31、目的地Harp 市( 乐团可多次在同一城市演出). 由于航线的费用和班次每天都在变, 城市和城市之间都有一份循环的航班表, 每一时间 , 每一方向 , 航班表循环的周期都可能不同. 现要求寻找一张花费费用最小的演出表. 输入 : 输入文件包括若干个场景. 每个场景的描述由一对整数n(2=n=10) 和 k(1=k=1000) 开始, 音乐家们要在这 n 个城市作巡回演出, 城市用 1.n标号 , 其中 1 是起点 Flute 市,n 是终点 Harp 市, 接下来有 n*(n-1)份名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -

32、 名师精心整理 - - - - - - - 第 7 页，共 27 页 - - - - - - - - - 航班表 , 一份航班表一行 , 描述每对城市之间的航线和价格, 第一组 n-1 份航班表对应从城市1 到其他城市(2,3,.n)的航班 , 接下的 n-1 行是从城市2 到其他城市 (1,3,4.n)的航班 ,如此下去 . 每份航班又一个整数d(1=d=30) 开始 , 表示航班表循环的周期, 接下来的 d 个非负整数表示1,2.d天对应的两个城市的航班的价格, 价格为零表示那天两个城市之间没有航班. 例如 3 75 0 80表示第一天机票价格是 75KOI, 第二天没有航班 , 第三天的

33、机票是80KOI, 然后循环 :第四天又是75KOI, 第五天没有航班 , 如此循环 . 输入文件由n=k=0 的场景结束 . 输出 : 对每个场景如果乐团可能从城市1 出发 , 每天都要飞往另一个城市, 最后 ( 经过 k 天) 抵达城市 n, 则输出这 k个航班价格之和的最小值. 如果不可能存在这样的巡回演出路线, 输出 0. 样例输入 : 3 6 2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0 样例输出 : 460 0 初看这道题 , 很

34、容易便可以想到动态规划, 因为第 x 天在第 y 个地方的最优值只与第x-1 天有关 , 符合动态规划的无后效性原则, 即只与上一个状态相关联, 而某一天 x 航班价格不难求出S=C(x-1) mod m +1.我们用天数和地点来规划用一个数组A1.1000,1.10来存储 ,Ai,j表示第 i 天到达第 j 个城市的最优值,Ci,j,l表示 i 城市与 j 城市间第 l 天航班价格 , 则 Ai,j=MinAi-1,l+Cl,j,i (l=1.n且Cl,j,i0),动态规划方程一出, 尽可以放怀大笑了. 示范程序 : program perform_hh; var f,fout:text;

35、p,l,i,j,n,k:integer; a:array 1.1000,1.10 of integer; 动态规划数组 c:array 1.10,1.10 of record 航班价格数组 num:integer; t:array 1.30 of integer; end; e:array 1.1000 of integer; procedure work; begin 人工赋第一天各城市最优值 for i:=1 to n do begin if c1,i.t10 then a1,i:=c1,i.t1; end; for i:=2 to k do begin for j:=1 to n do

36、begin for l:=1 to n do begin if (jl) and (cl,j.t(i-1) mod cl,j.num+10) 判断存在航班 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 27 页 - - - - - - - - - and (ai,j=0) or (ai-1,l+cl,j.t(i-1) mod cl,j.num+1ai,j) 判断比当前解优 then ai,j:=ai-1,l+cl,j.t(i-1) mod cl,j.num+1; 赋值

37、end; end; end; ep:=ak,n; 第 p 个场景的最优值 end; procedure readfile; 读文件 begin assign(f,PERFORM.DAT); reset(f); assign(fout,PERFORM.OUT); rewrite(fout); readln(f,n,k); p:=0; while (n0) and (k0) do begin p:=p+1; fillchar(c,sizeof(c),0); fillchar(a,sizeof(a),0); for i:=1 to n do begin for j:=1 to i-1 do begi

38、n read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; for j:=i+1 to n do begin read(f,ci,j.num); for l:=1 to ci,j.num do read(f,ci,j.tl); end; end; work; readln(f,n,k); end; 输出各个场景的解 for i:=1 to p-1 do writeln(fout,ei); write(fout,ep); close(f); close(fout); end; begin readfile; end. 四.

39、小结动态规划与穷举法相比, 大大减少了计算量, 丰富了计算结果,不仅求出了当前状态到目标状态的最优值, 而且同时求出了到中间状态的最优值, 这对于很多实际问题来说是很有用的. 这几年 , 动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位,每年省赛8 道题目中一般有23 道题目属于动态规划, 动态规划相比一般穷举也存在一定缺点: 空间占据过多 , 但对于空间需求量不大的题目来说, 动态规划无疑是最佳方法! 五. 课后题目1. m 个人抄 n 本书 , 每本书页数已知 , 每个人 ( 第一个人除外 ) 都必须从上一个人抄的最后一本书的下一本抄起 ( 书必须整本整本的抄), 求一种分配方法,

40、 使抄书页数最多的人抄书页数尽可能少. (GDOI99 Books). 2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 27 页 - - - - - - - - - （GDKOI2000 Compress) 3. Canada 境内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouver.，各个城市之间可能有航班相连，也可能没有，现要求从最西的城市出

41、发，自西向东到达最东的城市，再返回最西的城市，除最西城市外，其他每个城市只能访问一次，求最多能访问多少个城市（七）习题1. 数列的整除性 (Divisibility) 提交文件名： div.exe 问题描述：对于任意一个整数数列，我们可以在每两个整数中间任意放一个符号+或- ，这样就可以构成一个表达式，也就可以计算出表达式的值。比如，现在有一个整数数列：17，5，-21 ，-15，那么就可以构造 8 个表达式： 17+5+(-21)+15=16 17+5+(-21)-15=14 17+5-(-21)+15=58 17+5-(-21)-15=28 17-5+(-21)+15=6 17-5+(-2

42、1)-15=-24 17-5-(-21)+15=48 17-5-(-21)-15=18 对于一个整数数列来说，我们能通过如上的方法构造不同的表达式，从而得到不同的数值，如果该数值能够被 k 整除。在上面的例子中，该数列能被7 整除 (17+5+(-21)-15=-14)，但不能被5 整除。现在你的任务是，判断某个数列是否能被某数整除。输入格式：数据存放在当前目录下的文本文件“div.in”中。文件的第一行是一个整数M ，表示有 M个子任务。接下来是m个子任务的描述。每个子任务有两行。第一行是两个整数n 和 K（1=n=1000, 2=k=100 ）， n 和 k 中间有一个空格。n 表示数列中

43、整数的个数；k 就是需要你判这个数列是否能被k 整除。第二行是数列的n 个整数，整数间用空格隔开，每个整数的绝对值都不超过10000。输出格式：答案输出到当前目录下的文本文件“div.out中。输出的文本应有M行，依次对应输入文件中的M个子任务，若数列能被K整除则输出 Divisible，否则输出 Not Divisible。首行行末应没有空格。* 输入输出样例：输入文件： div in 输出文件： div out 2 Divisible 4 7 Not Divisible17 5 -21 15 4 5 17 5 -21 15 2. 背包问题设有种物品，每种物品有一个重量及一个价值。但每种物品

44、的数量是无限的，同时有一个背包，最大载重量为，今从种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于，而价值的和为最大。输入数据：第一行两个数：物品总数，背包载重量；两个数用空格分隔；第二行 N 个数 , 为种物品重量；两个数用空格分隔；第三行 N 个数 , 为 N 种物品价值 ; 两个数用空格分隔；输出数据：第一行总价值；以下 N行，每行两个数，分别为选取物品的编号及数量；输入样例：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 27 页 - - -

45、- - - - - - 4 10 2 3 4 7 1 3 5 9 输出样例：12 2 1 4 1 前提贪心法（它是一种多步决策法，它总是作出在当前看来是最好的选择，它的考虑不是从整体出发，而只是某种意义上的局部最优，这样贪心法不能对所有问题达到整体最优解，但是对相当范围的许多问题都能够产生整体最优解。- 译者）动态规划（它是将问题进行逐步的划分来缩小问题的规模，直到可以求出子问题的解为止。分划子问题后，对应的子问题中含有大量的重复，这样就将重复地求解；在第一次遇到重复时把它解决，并将解保存起来，以备后面引用。动态规划法常用来求一个问题在某种意义下的最优解。- 译者）递归下降3. 用录音带录音农

46、场主约翰最喜欢的爱好是制作一个Bessie 喜欢的音乐合集磁带以便它在产奶时听。Bessie 的产奶量取决于它产奶时所听的歌曲。已知一组歌曲（每首歌都由一对整数此曲的长度（以秒计），听该首歌时的产奶量来表示）以及给挤奶的总时间。找到这样一组歌曲的集合，使得歌曲的总长度不超过给Bessie 挤奶的总时间且使Bessie 的产奶量达到最大。抽象描述已知一组物品 - 每个都有其尺寸和值（比如，重量），以及可用的总空间。找到这样一个集合，使得该集合的值的和最大，且其尺寸的和受某些限制所约束。集合中任何一个特定的项目的总数目/ 尺寸不能超过它的可利用率。解题想法视其为背包问题的一般方法是一个容量受限的背

47、包使得放入其中的物品的值达到最大。以上述问题为例，Bessie 产奶时听的音乐带就是“背包”，而那些歌就是“放入背包中的物品”。4. 三个背包问题背包问题有三种形式：小数背包问题允许将小数表示的物品放入背包中的是小数背包问题。举例来说，如果物品是原油、飞机燃料、煤油而你的背包是一只水桶，取0.473 升的原油， 0,263 升的飞机燃料和0,264 升的煤油就是有意义的。这是形式最简单的要解决的背包问题。整数背包问题在整数背包问题中，只有完整的物品能放入背包里。此形式的一个例子就是：部分的曲子不允许放入包中。多重背包问题在多重背包问题中，需被填充的背包多于一个。如果允许有小数的物品放入，也就等

48、于有一个大的背包，其容量相当于所有可用背包的和。因此，此术语只用来指多重整数背包的情况。小数背包问题小数背包问题是三者中最简单的，其贪婪解法如下：找到“值密度”（物品值/ 尺寸）最大的物品如果总容量仍就超过物品的可利用率，把所有满足条件的物品放入背包中，然后反复执行。如果总容量少于物品的可利用率，尽可能多的使用可用空间，然后终止。由于这个算法必须先按照值密度把物品分类，然后以降序将它们放入背包，直至容量用完，该算法以N 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 2

49、7 页 - - - - - - - - - log N 级运行。通常简单些的方法不是将它们分类，而是不停地找每次不用的最大值密度，这种算法的时间复杂度是 O(N 2) 。注意：对于这类问题，因为你可以做一个微小的变换使得所有的物品尺寸大小为一，且原始尺寸大小和可利用率（当然用原始尺寸大小除值）的乘积就是总容量，同时有尺寸和可利用率是很少见的。延伸：在这种情况下，物品的值和可利用率可以是实数。用这种算法处理有小数的尺寸大小也不是问题。整数背包问题这个问题有点难度，但是如果背包足够小，使用动态规划，它还是可解的。依据背包大小的最大值设计动态的程序。刷新用来表示大小为S的物品的数组，颠倒其次序，看将

50、当前物品放入大小为K的背包中所产生的集合是否比当前最好的大小为K+S的背包更符合条件。这个算法运行K*N 次，其中 K 是背包的大小， N 是物品的可利用率义之和。如果背包太大了以至于无法分配此数组，递归下降是一种选择，即这个问题是NP完全的（给定I 上的一个语言 L，如果有一架非确定图灵机M和一个多项式P(n) ，对任何 I 上的长度为n 的串 w ，M都可以在P(n) 步内确定是否接受w，则称 L 是非确定图灵机下多项式时间复杂性问题，简记为NP问题 / 语言。若 L是属于 NP的，且对 NP中的每一个语言L ，都存在一个从L 至 L 的多项式时间转化，我们说L 是 NP完整的。 - 译者