当前位置:文档之家 > 动态规划讲义

动态规划讲义

动态规划

(一)动态规划的基本思想

一、动态规划含义:

在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果。因此,各个阶段决策确定后,组成一个决策序列,因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策过程,这种问题称为多阶段决策问题。

在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,我们称这种解决多阶段决策最优化的过程为动态规划。

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

二、设计动态规划法的步骤:

1、找出最优解的性质,并刻画其结构特征;

2、递归地定义最优值(写出动态规划方程);

3、以自底向上的方式计算出最优值;

4、根据计算最优值时得到的信息,构造一个最优解。

步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤4可以省略,步骤3中记录的信息也较少;若需要求出问题的一个最优解,则必须执行步骤4,步骤3中记录的信息必须足够多以便构造最优解。

三、动态规划问题的特征:

动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段。

动态规划算法的有效性依赖于问题本身所具有的两个重要性质:最优子结构性质和子问题重叠性质。

动态规划一般还存在一条或多条状态转移方程。

1、最优子结构:当问题的最优解包含了其子问题的最优解时,称该问题具有最优子结构性质。

2、重叠子问题:在用递归算法自顶向下解问题时,每次产生的子问题并不总是新问题,有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质,对每一个子问题只解一次,而后将其解保存在一个表格中,在以后尽可能多地利用这些子问题的解。

(二)动态规划算法的基本步骤

设计一个标准的动态规划算法,通常可按以下几个步骤进行:

1、划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。

2、选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。

3、确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。

4、写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。

动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下:

标准动态规划的基本框架

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):=t; {计算fk(xk)的最优值}

end;

9.t:=一个极值; {∞或-∞}

10.for 每一个x1∈X1 do

11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}

12.输出t;

但是,实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个步骤进行:

1.分析最优解的性质,并刻划其结构特征。

2.递归地定义最优值。

3.以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。

4.根据计算最优值时得到的信息,构造一个最优解。

步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此时,在步骤(3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的信息,快速地构造出一个最优解。

(三)动态规划概述

1.基本思想:将问题分解为若干小问题,解子问题,然后从子问题得到原问题的解。

2.特点:将问题分解为子问题,这些子问题往往不相互独立。(如果可以用分治法求解,分解的子问题太多,因此,用分治法时间代价太高,消耗指数时间)

3.且某些子问题可能被重复多次计算,因此将计算过的子问题的结果保存。一般,放入表中。

4.应用:往往求解具有某种最优性质的问题,此类问题往往具有多个解,我们要找到具有最优值的那个解。

5.步骤:

找出最优解的性质,刻画其特征;

递归地定义最优值;

以自底向上的方式计算出最优值;

根据计算最优值时得到的信息,构造一个最优解。

(四)动态规划问题中的术语

阶段:把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同。描述阶段的变量称为阶段变量。在多数情况下,阶段变量是离散的,用k表示。此外,也有阶段变量是连续的情形。如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。

在前面的例子中,第一个阶段就是点A,而第二个阶段就是点A到点B,第三个阶段是点B到点C,而第四个阶段是点C到点D。

状态:状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。在上面的例子中状态就是某阶段的出发位置,它既是该阶段某路的起点,同时又是前一阶段某支路的终点。

在前面的例子中,第一个阶段有一个状态即A,而第二个阶段有两个状态B1和B2,第三个阶段是三个状态C1,C2和C3,而第四个阶段又是一个状态D。

过程的状态通常可以用一个或一组数来描述,称为状态变量。一般,状态是离散的,但有时为了方便也将状态取成连续的。当然,在现实生活中,由于变量形式的限制,所有的状态都是离散的,但从分析的观点,有时将状态作为连续的处理将会有很大的好处。此外,状态可以有多个分量(多维情形),因而用向量来代表;而且在每个阶段的状态维数可以不同。

当过程按所有可能不同的方式发展时,过程各段的状态变量将在某一确定的范围内取值。状态变量取值的集合称为状态集合。

无后效性:我们要求状态具有下面的性质:如果给定某一阶段的状态,则在这一阶段以后过程的发展不受这阶段以前各段状态的影响,所有各阶段都确定时,整个过程也就确定了。换句话说,过程的每一次实现可以用一个状态序列表示,在前面的例子中每阶段的状态是该线路的始点,确定了这些点的序列,整个线路也就完全确定。从某一阶段以后的线路开始,当这段的始点给定时,不受以前线路(所通过的点)的影响。状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展,这个性质称为无后效性。 决策:一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。在最优控制中,也称为控制。在许多间题中,决策可以自然而然地表示为一个数或一组数。不同的决策对应着不同的数值。描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。

决策变量的范围称为允许决策集合。

策略:由每个阶段的决策组成的序列称为策略。对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。允许策略集合中达到最优效果的策略称为最优策略。

给定k阶段状态变量x(k)的值后,如果这一阶段的决策变量一经确定,第k+1阶段的状态变量x(k+1)也就完全确定,即x(k+1)的值随x(k)和第k阶段的决策u(k)的值变化而变化,那么可以把这一关系看成(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的最短路径……──事实正是如此,因此我们认为这个例子满足最优性原理的要求。

(五)标号法

标号法是一种最佳算法,多用于求图的最短路问题。

一、标号法的概念:

所谓标号,是指与图的每一个顶点相对应的一个数字。标号法可以说是动态规划,它采用顺推的方法,对图的每一边检测一次,没有重复的回溯搜索,因此标号法是一种最佳算法。

二、标号法的算法流程:

现有一图G,求从起点Vs到终点Ve的最短距离。设:

Sum(j)───顶点Vj的标号,代表的是Vs到Vj的最短距离。

Vj 已标味着Vs到Vj的最短路以及这条路径的长度已求出。

M(i,j)───Vi到Vj的非负长度。

H(j)───顶点Vj的前趋结点。标号法的算法流程如下:

sum(s)←0

Vs进入队列L

-----→移出队列L的队首Vk←-----

| ↓ |

| Vk是不是Ve------------------|---→计算结束打印路径

| N∣ Y |

| ↓ |

| 由Vk扩展出结点Vj |

| (Vk与Vj之间相连) |

| Sj←Sum(k)+M(k,j) |

| ↓ |

| Sj小于Sum(j) |

| | |

| Y | N |

| | --------------------

| |

| ↓

| Sum(j)←Sj

| H(j)← Vk

| Vj加入队列L并对队列L按Sum值由小到大排序

| ↓

---------------

注意:1.只有两个顶点间的距离为非负时,才可用标号法。

2.只有队列的首结点是目标结点时,才可停止计算。否则得出的不一定是最优解。

三、例题解析:

1.相邻项序列(GDOI97第四题)

[问题描述]:对于一个N*N(N<=100)的正整数矩阵M,存在从M[A1,B1]开始到M[A2,B2]结束的相邻项序列.两个项M[I,J]和M[K,L]相邻的件是指满足如下情况之一:

(1)I=K+-1和J=L

(2)I=K和J=L+-1。

[任务]:从文件中输入矩阵M,再读入K(K<=4)组M[A1,B1]和M[A2,B2]的值。对于每一组M[A1,B1]和M[A2,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

[解析]:本题若将相邻的两个数看作是两个顶点,两个数之差的绝对值作为权,则问题转

化成求两个顶点的最短路问题。

设:sum[I,J]为从起点Vs到结点M[I,J]的最短距离。H[I,J]记录结点M[I,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 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;

begin

flag:=true; a:=1;

c[a]:=m[x2,y2];

x:=x2; y:=y2;

while flag do

begin

a:=a+1; x3:=x; y3:=y;

x:=h[x3,y3,1]; y:=h[x3,y3,2];

c[a]:=m[x,y];

if(x=x1) and (y=y1) then flag:=false;

end; {求出整条路径,放入数组C中}

writeln(f2,zz,' ',sum[x2,y2]);

for b:=a downto 1 do write(f2,c[b],' '); {打印结果}

writeln(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 sum[g^.x,g^.y]>sum[x,y] then

begin

e^.next:=g; f^.next:=e;

flag:=false; a:=i; {加入队列}

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}

sum[xz,yz]:=0; {置起点Sum值为0}

flag:=true;

new(e);

e^.x:=xz; e^.y:=yz;

new(l);

l^.next:=e; {起点进入队列}

c:=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

x1:=x+fang[a,1];

y1:=y+fang[a,2];

if(x1>0) and (x1<=n) and (y1>0) and (y1<=n) then

begin

sj:=sum[x,y]+abs (m[x,y]-m[x1,y1]);

if(sj

begin

sum[x1,y1]:=sj;

h[x1,y1,1]:=x; h[x1,y1,2]:=y; {记录路径}

add(x1,y1,c,l); {将新扩展出来的结点进入队列}

c:=c+1; {结点个数加一}

end;

end;

end;

end;

end;

print;{打印结果}

end;

begin

assign(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,m[a,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.

四、小结

综上所述,标号法是动态规划的一种,它采用顺推的方法,对图的每一边检测一次,没有重复的回溯搜索,要比一般的搜索优秀得多。它是一种最佳算法。

(六)动态规划例题

1、Catcher防卫导弹(GDOI'98)

题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列。这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础的题目,用一个二维数组C[1..Max,1..2]来建立动态规划状态转移方程(注:C[1..Max,1]表示当前状态最多可击落的导弹数,C[1..Max,2]表示当前状态的前继标志):

Ci=Max{C[j]+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..4000,1..2] of integer; {动态规划数组}

procedure readfile;

begin

assign(f,'catcher.dat'); reset(f);

readln(f,num);

for i:=1 to num do readln(f,a[i]);

end;

procedure work;

begin

fillchar(c,sizeof(c),0); c[num,1]:=1; {清空数组,赋初值} {开始进行动态规划}

for i:=num-1 downto 1 do

begin

n:=0; max:=1;

for j:=i+1 to num do

if(a[i]>a[j]) and (max<1+c[j,1])

then

begin

n:=j;

max:=1+c[j,1];

end;

c[i,1]:=max; c[i,2]:=n;

end;

writeln;

writeln('Max : ',max); {打印最大值}

max:=0; n:=0;

for i:=1 to num do

if c[i,1]>max then

begin

max:=c[i,1];

n:=i;

end;

{返回寻找路径}

repeat

writeln(n,' ');

n:=c[n,2];

until n=0;

end;

begin

readfile;

work;

end.

2、Perform巡回演出(GDKOI'2000)

[问题描述]:Flute市的Phlharmoniker乐团2000年准备到Harp市做一次大型演出,本着普及古典音乐的目的,乐团指挥L.Y.M准备在到达Harp市之前先在周围一些小城市作一段时间的巡回演出,此后的几天里,音乐家们将每天搭乘一个航班从一个城市飞到另一个城市,最后才到达目的地Harp市(乐团可多次在同一城市演出)。

由于航线的费用和班次每天都在变,城市和城市之间都有一份循环的航班表,每一时间,每一方向,航班表循环的周期都可能不同。现要求寻找一张花费费用最小的演出表。

[输入]:输入文件包括若干个场景。每个场景的描述由一对整数n(2<=n<=10)和k

(1<=k<=1000)开始,音乐家们要在这n个城市作巡回演出,城市用1..n标号,其中1是起点Flute市,n是终点Harp市,接下来有n*(n-1)份航班表,一份航班表一行,描述每对城市之间的航线和价格,第一组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,第二天没有航班,第三天的机票是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

[问题分析]:初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C[(x-1) mod m +1]。我们用天数和地点来规划用一个数组

A[1..1000,1..10]来存储,A[i,j]表示第i天到达第j个城市的最优值,C[i,j,l]表示i 城市与j城市间第l天航班价格,则A[i,j]=Min{A[i-1,l]+C[l,j,i](l=1..n且

C[l,j,i]<>0),动态规划方程一出,尽可以放怀大笑了。

[参考程序]:

program perform_hh;

var f,fout:text;

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 c[1,i].t[1]<>0 then a[1,i]:=c[1,i].t[1];

end;

for i:=2 to k do

begin

for j:=1 to n do

begin

for l:=1 to n do

begin

if(j<>l) and (c[l,j].t[(i-1) mod c[l,j].num+1]<>0) {判断存在航班} and ((a[i,j]=0) or (a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]

end;

end;

e[p]:=a[k,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 (n<>0) and (k<>0) 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

begin

read(f,c[i,j].num);

for l:=1 to c[i,j].num do read(f,c[i,j].t[l]);

end;

for j:=i+1 to n do

begin

read(f,c[i,j].num);

for l:=1 to c[i,j].num do read(f,c[i,j].t[l]);

end;

end;

work;

readln(f,n,k);

end;

{输出各个场景的解}

for i:=1 to p-1 do writeln(fout,e[i]);

write(fout,e[p]);

close(f);

close(fout);

end;

begin

readfile;

end.

(七)动态规划小结

动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说是很有用的。这几年,动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位,每年省赛8道题目中一般有2~3道题目属于动态规划,动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法!

(八)动态规划习题

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+(-21)-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表示数列中整数的个数;k就是需要你判这个数列是否能被k整除。第二行是数列的n个整数,整数间用空格隔开,每个整数的绝对值都不超过10000。

[输出格式]:

答案输出到当前目录下的文本文件“div.out"中。

输出的文本应有M行,依次对应输入文件中的M个子任务,若数列能被K整除则输出“Divisible”,否则输出“Not Divisible”。首行行末应没有空格。

[输入输出样例]:

输入文件:div.in:

2

4 7

17 5 -21 15

4 5

17 5 -21 15

输出文件:div.out:

Divisible

Not Divisible

2.背包问题

[问题描述]:设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为xk,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于xk,而价值的和为最大。

[输入数据]:

第一行两个数:物品总数n,背包载重量xk;两个数用空格分隔;

第二行n个数,为n种物品重量;两个数用空格分隔;

第三行n个数,为n种物品价值;两个数用空格分隔;

[输出数据]:

第一行总价值;

以下n行,每行两个数,分别为选取物品的编号及数量;

[输入样例]:

4 10

2 3 4 7

1 3 5 9

[输出样例]:

12

2 1

4 1

[算法提示]:

(1)贪心法(它是一种多步决策法,它总是作出在当前看来是最好的选择,它的考虑不是从整体出发,而只是某种意义上的局部最优,这样贪心法不能对所有问题达到整体最优解,但是对相当范围的许多问题都能够产生整体最优解。)

(2)动态规划(它是将问题进行逐步的划分来缩小问题的规模,直到可以求出子问题的解为止。分划子问题后,对应的子问题中含有大量的重复,这样就将重复地求解;在第一次遇到重复时把它解决,并将解保存起来,以备后面引用。动态规划法常用来求一个问题在某种意义下的最优解。)

(3)递归下降

3.用录音带录音

[问题描述]:农场主约翰最喜欢的爱好是制作一个Bessie喜欢的音乐合集磁带以便它在产奶时听。Bessie的产奶量取决于它产奶时所听的歌曲。

已知一组歌曲(每首歌都由一对整数——此曲的长度(以秒计),听该首歌时的产奶量来表示)以及给挤奶的总时间。找到这样一组歌曲的集合,使得歌曲的总长度不超过给Bessie挤奶的总时间且使Bessie的产奶量达到最大。

[抽象描述]:已知一组物品--每个都有其尺寸和值(比如,重量),以及可用的总空间。找到这样一个集合,使得该集合的值的和最大,且其尺寸的和受某些限制所约束。集合中任何一个特定的项目的总数目/尺寸不能超过它的可利用率。

[解题想法]:视其为背包问题的一般方法是一个容量受限的背包使得放入其中的物品的值达到最大。

以上述问题为例,Bessie产奶时听的音乐带就是“背包”,而那些歌就是“放入背包中的物品”。

4.三个背包问题

[问题描述]:背包问题有三种形式:

●小数背包问题

允许将小数表示的物品放入背包中的是小数背包问题。举例来说,如果物品是原油、飞机燃料、煤油而你的背包是一只水桶,取0.473升的原油,0,263升的飞机燃料和0,264升的煤油就是有意义的。这是形式最简单的要解决的背包问题。

●整数背包问题

在整数背包问题中,只有完整的物品能放入背包里。此形式的一个例子就是:部分的曲子不允许放入包中。

●多重背包问题

在多重背包问题中,需被填充的背包多于一个。如果允许有小数的物品放入,也就等于有一个大的背包,其容量相当于所有可用背包的和。因此,此术语只用来指多重整数背包的情况。

①小数背包问题

小数背包问题是三者中最简单的,其贪婪解法如下:

●找到“值密度”(物品值/尺寸)最大的物品

●如果总容量仍就超过物品的可利用率,把所有满足条件的物品放入背包中,然后反复执行。

●如果总容量少于物品的可利用率,尽可能多的使用可用空间,然后终止。

●由于这个算法必须先按照值密度把物品分类,然后以降序将它们放入背包,直至容量用完,该算法以nlogn级运行。通常简单些的方法不是将它们分类,而是不停地找每次不用的最大值密度,这种算法的时间复杂度是O(n2) 。

注意:对于这类问题,因为你可以做一个微小的变换使得所有的物品尺寸大小为一,且原始尺寸大小和可利用率(当然用原始尺寸大小除值)的乘积就是总容量,同时有尺寸和可利用率是很少见的。

延伸:在这种情况下,物品的值和可利用率可以是实数。用这种算法处理有小数的尺寸大小也不是问题。

②整数背包问题

这个问题有点难度,但是如果背包足够小,使用动态规划,它还是可解的。

●依据背包大小的最大值设计动态的程序。

●刷新用来表示大小为S的物品的数组,颠倒其次序,看将当前物品放入大小为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完整的。)。当然,递归下降在以小的物品填充的大背包情况下可以运行相当长的一段时间。

延伸:

●小数的值不是问题;数组可以用实数数组来代替整数数组。小数的可利用率并不影响什么,在没有大量损失的条件下,缩短数字(如果你有3,5个物品,你可以仅用3)。

●小数的尺寸是个讨厌的东西,它使得问题递归下降。

●如果尺寸都相同,问题就能贪婪地解开,在下降的值排序中选择物品,直到背包满为止。

●如果值都是1.0,同样地使用贪心法,在上升的尺寸大小排序中选择物品,直到背包满为止。

③多重背包问题

对于任何大小的多重背包,状态空间太大了以至于无法使用从整数背包算法中来的DP解法。于是递归下降是解决这个问题的方法。

延伸:

●用递归下降,通常扩展就简单了。小数的尺寸和值就不是问题了,同样地值的计算功能也不是问题。

●如果值都是同一个,那么如果能被放入所有背包中的物品的最大值是n,则存在使用n 个最小物品的解法。它能大大减少查找时间。

5.分数膨胀[1998 USACO National Championship]

[问题描述]:你正试图设计一个有最高分数(<10,000)的比赛。已知比赛长度,一组问题,问题的长度以及每个问题的分值,计算满足长度约束的最高分数的比赛。

[分析]:这是一个整数背包问题,比赛是背包,尺寸是问题的长度,值是分数值。背包(比赛)尺寸的限制是其足够小使得解法在存储器中运行。

6.篱笆栏[1999 USACO Spring Open]

[问题描述]:农场主约翰准备在他的领地建一圈篱笆。他已装好了柱子,所以他知道所要的围栏长度。当地的木材店有各种长度的木板(至多50个)。已知木材店木板的长度,约翰要的围栏长度,计算约翰建篱笆所用的围栏最大值。

[分析]:这是个多重背包问题,木材店的木板是背包,物品是约翰用的围栏。物品的尺寸就是长度,值是一。由于值都是一,如果存在用任意K个围栏的解法,则有用K个最小围栏的解法。

7.装满你的油箱

[问题描述]:你在Beaver郡中部一百英里有一个加油站的城市中,想将你的油箱装满好能到达Rita Blanca。幸运地是,这个小镇有两三个加油站,但它们的油都好像要用光了。已知每个加油站的油价,每个加油站的油量,计算为了花最少的钱,应该从每个加油站买多少汽油。

分析:这是一个小数背包问题,背包是油箱,物品是汽油。

8.求函数最大值

[问题描述]:已知3个函数A,B,C值如下表示,自变量取值为0—10的整数。请用动态规划的方法求出一组x,y,z,使得A(x)+B(y)+C(z)为最大,并且满足x2+y2+z2

x 0 1 2 3 4 5 6 7 8 9 10

A(x) 2 4 7 11 13 15 18 22 18 15 11

B(x) 5 10 15 20 24 18 12 9 5 3 1

C(x) 8 12 17 22 19 16 14 11 9 7 4

9.石子合并

[问题描述]:在一个圆形操场的四周摆放着n堆石子(n<=100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆栈数n及每堆栈的石子数(n<=20)。

(1)选择一种合并石子的方案,使用权得做n-1次合并,得分的总和最小;

(2)选择一种合并石子的方案,使用权得做n-1次合并,得分的总和最小;

[输入数据]:

第一行为石子堆数n;

第二行为每堆的石子数,每两个数之间用一个空格分隔。

[输出数据]:

从第一至第n行为得分最小的合并方案。第n+1行是空行。从第n+2行到第2n+1行是得分最大合并方案。每种合并方案用n行表示,其中第i行(1<=i<=n)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆先输出均可)。要求将待合并的两堆石子数以相应的负数表示。

[输入输出范例]:

输入:

4

4 5 9 4

输出:

-4 5 9 -4

-8 -5 9

-1 3 -9

2 2

4 -

5 -9 4

4 -1 4 -4

-4 -1 8

2 2

10.最小代价子母树

[问题描述]:设有一排数,共n个,例如:22 14 7 13 26 15 11。任意2个相邻的数可以进行归并,归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小。

输入、输出数据格式与“石子合并”相同。

[输入样例]:

4

12 5 16 4

[输出样例]:

-12 -5 16 4

17 -16 -4

-17 -20

37

11.商店购物

[问题描述]:某商店中每种商品都有一个价格。例如,一朵花的价格是2 ICU(ICU是信息学竞赛的货币的单位);一个花瓶的价格是5 ICU。为了吸引更多的顾客,商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是5 ICU;2个花瓶加1朵花是10 ICU不是12 ICU。

编一个程序,计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意,你不能变更顾客所购商品的种类及数量,即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述,并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:

1朵花加2个花瓶:优惠价:10 ICU

2朵花正常价:4 ICU

[输入数据]:

用两个文件表示输入数据。第一个文件INPUT.TXT描述顾客所购物品(放在购物筐中);第二个文件描述商店提供的优惠商品及价格(文件名为OFFER.TXT)。两个文件中都只用整数。

第一个文件INPUT.TXT的格式为:第一行是一个数字B(0≤B≤5),表示所购商品种类数。下面共B行,每行中含3个数C,K,P。C 代表商品的编码(每种商品有一个唯一的编码),1≤C≤999。K代表该种商品购买总数,1≤K≤5。P 是该种商品的正常单价(每件商品的价格),1≤P≤999。请注意,购物筐中最多可放5*5=25件商品。

第二个文件OFFER.TXT的格式为:第一行是一个数字S(0≤S≤99),表示共有S 种优惠。下面共S行,每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对(C,K),其中C代表商品编码,1≤C≤999。K代表该种商品在此组合中的数量,1≤K≤5。本行最后一个数字P(1≤P≤9999)代表此商品组合的优惠价。当然,优惠价要低于该组合中商品正常价之总和。

[输出数据]:

在输出文件OUTPUT.TXT中写一个数字(占一行),该数字表示顾客所购商品(输入文件指明所购商品)应付的最低货款。

[输入输出数据举例]:

┌────────┐ ┌────────────┐ ┌────────┐

│ INPUT.TXT │ │ OFFER.TXT │ │ OUTPUT.TXT │

├────────┤ ├────────────┤ ├────────┤

│ 2 │ │ 2 │ │ 14 │

│ 7 3 2 │ │ 1 7 3 5 │ │ │

│ 8 2 5 │ │ 2 7 1 8 2 10 │ │ │

└────────┘ └────────────┘ └────────┘

12.任务名:PREFLX

[问题描述]:一些生物体的复杂结构可以用其基元的序列表示,而一个基元用一个大写英文字符串表示。生物学家的一个问题就是将一个这样的长序列分解为基元(字符串)的序列,对于给定的基元的集合P,如果可以从中选出N个基元P1,P2,…Pn,将它们各自对应的字符串依次联接后得到一个字符串S,称S可以由基元集合P构成。在从P中挑选基元时,一个基元可以使用多次,也可以不用,例如,序列ABABACABAB可以由基元集合{A,AB,BA,CA,BBC}构成。

字符串的前K个字符称为该字符串的前缀,其长度为K。请写一个程序,对于输入的基元集合P和字符串T,求出一个可以由基元集合P构成的字符串T的前缀,要求该前缀的长度尽可能的长,输出其长度。

[输入数据]:

有两个输入文件INPUT.TXT和DATA.TXT。

INPUT.TXT的第一行是基元集合P中基元的数目N(1<=N<=100),阴÷随后有2N行,每两行描述一个基元。第一行为该基元的长度L(1<=L<=20)。随后一行是一个长度为L 的大写英文字符串,表示该基元。每个基元互不相同。

文件DATA.TXT描述要处理的字符串T,每一行行首有一个大写英文字母,最后一行是一个字符“.”,表示字符串结束。T的长度最小为1,最大不超过500000。

[输出数据]:

文件名OUTPUT.TXT只有一行,是一个数字,表示可以由P构成的T的最长前缀的长度。

[输入输出示例]:

图1给出了两个输入文件和相应的输出文件。

简析:

算法:动态规划

数据结构:字符串

题型:II型

难度:4分

[编程时间]:4分钟。

简述:本题竞赛时有一个很长的文件测试数据,用动态规划可较快的出答案。

13.旅游预算

[问题描述]:一个旅行社需要估算乘汽车从某城市到另一城市的最小费用,沿路有若干加油站,每个加油站收费不一定相同。

旅游预算有如下规则:

若油箱的油过半,不停车加油,除非油箱中的油不可支持到下一站;每次加油时都加满;在一个加油站加油时,司机要花费2元买东西吃;司机不必为其他意外情况而准备额外的油;汽车开出时在起点加满油箱;计算精确到分(1元=100分)。

编写程序估计实际行驶在某路线所需的最小费用。

[输入格式]:

从当前目录下的文本文件“route.dat”读入数据。按以下格式输入若干旅行路线的情况:

第一行为起点到终点的距离(实数)

第二行为三个实数,后跟一个整数,每两个数据间用一个空格隔开。其中第一个数为汽车油箱的容量(升),第二个数是每升汽油行驶的公里数,第三个数是在起点加满油箱的费用,第四个数是加油站的数量。(<=50)。接下去的每行包括两个实数,每个数据之间用一个空格分隔,其中第一个数是该加油站离起点的距离,第二个数是该加油站每升汽油的价格(元/升)。加油站按它们与起点的距离升序排列。所有的输入都有一定有解。

[输出格式]:

答案输出到当前目录下的文本文件“route.out”中。

该文件包括两行。第一行为一个实数和一个整数,实数为旅行的最小费用,以元为单位,精确到分,整数表示途中加油的站的N。第二行是N个整数,表示N个加油的站的编号,按升序排列。数据间用一个空格分隔,此外没有多余的空格。

[输入输出举例]:

输入文件:(route.dat)

516.3

15.7 22.1 20.87 3 2

125.4 1.259

297.9 1.129

345.2 0.999

输出文件(route.out)

38.09 1

13.海上交通控制

[问题描述]:海上交通图可以用一个有向图来表示,顶点表示港口,边表示两个港口之间是否有航线可通。为保证海上交通安全和以尽量快的速度到达目的地,每艘船在出发前都将航行计划(包括出发时间、速度、出发与到达港口)提交给海上交通控制局,由海上交通控制局为它们制定航线。现给出一系列的船只航行计划(包括出发时间、速度、出发与到达港口),请你根据以下原则编程为它们制定航线:

1.每艘船在出发的一瞬间提交航行计划(提交和出发的时间差可以忽略);

2.每艘船都严格按照出发时间出发,不能提前,也不能延迟;

3.在任何时间一条航道(两港口间的直达航线)上只能有一艘船,因此,一艘船在出发的瞬间发现某航道将在末来的某段时间内会被在它之前出发的船占用,则它在那一段时间内将不会使用该航道,当然其余时间还是可以使用该航道;

4.每个港口均可被无限艘船同时使用;

5.在满足上述条件后,要使本船航行的时间最短;

6.假如某船不能到达目标港口,那么它将放弃这个航程;

7.船在任何时候都不能停下来,即从出发后,要一直航行到目的地,中途不得在航道或港口中停留。

时间用4位数字表示如2345表示23:45,速度单位用节(海里/小时)表示。在计算时间时,中间结果应是精确的时间(即不要四舍五入到分钟),而航行时间的计算是以总距离除以速度为准,最终到目标地的时刻应是航行时刻加上航行时间的四舍五入到分钟的结果。

[输入格式]:

从当前目录下的文本文件“LANE.DAT”读入数据。输入的数据一定有解,且不会出现跨越00:00的情况,例如,一艘船在23:55出发,第二天0:15到达的情况是不会出现的。输入文件开头是港口定义:

第一行是港口数N(N<=26〉;

第二行是一个长度为N的大写字母串,每个字母表示一个港口名字;

第三行开始N行的N X N矩阵是一个邻接矩阵,每行有N个整数,其值为港口间距离(单位为海里),整数间以空格分隔(若为0表示两港口没有直达航线相连);

接着的一行是一个整数M(M<=50),表示共有M艘船提交航行计划;

接下去的每3行表示一艘船的航行计划,其中第一行是船名,第二行是出发时间和航速,两者均为整数,以一个空格分隔,第三行是两个大写安母,之间没有任何分隔,第一个表示出发的港口,第二个表示目的港口;

[输出格式]:

答案输出到当前目录下的文本文件“LANE.OUT”中。该文件的每3行表示一艘船的航线,其中第一行是船名,第二行是出发时间和到达时间,两者均为整数,以一个空格分隔,第三行是数个大写字母,之间没有任何分隔,表示该船经过的港口(包括出发和目的港口)。如果这艘船放弃航程时,到达时间用-1来表示,并留空第三行。

注意:在输入和输出中航行计划和航线均按出发时间排序,时间精确到分钟。

[输入输出举例]:

输入文件:LANE.DAT 输出文件:LANE.OUT

5 Bluesky

ABCDE 800 1000

0 10 0 50 10 CB

10 0 20 70 0 Blackhorse

0 20 0 20 0 900 1100

50 70 20 0 10 AB

10 0 0 10 0 Greenforest

4 1000 1130

Bluesky DEAB

0800 10 Silverboat

CB 1200 1300

Blackhorse DC

0900 5

AB

Greenforest

1000 20

DB

Silverboat

1200 20

DC

15.太平王世子事件后,陆小凤成了皇上特聘的御前一品侍卫。

[问题描述]:皇宫以午门为起点,直到后宫嫔妃们的寝宫,呈一棵树的形状;某些宫殿间可以互相望见。大内保卫森严,三步一岗,五步一哨,每个宫殿都要有人全天候看守,在不同的宫殿安排看守所需的费用不同。

可是陆小凤手上的经费不足,无论如何也没法在每个宫殿都安置留守侍卫。

[编程任务]:帮助陆小凤布置侍卫,在看守全部宫殿的前提下,使得花费的经费最少。

[数据输入]:

输入数据由文件名为INPUT.TXT的文本文件提供。输入文件中数据表示一棵树,描述如下:

第1行 n,表示树中结点的数目。

第2行至第n+1行,每行描述每个宫殿结点信息,依次为:该宫殿结点标号i

(0

对于一个n(0

[数据输出]:输出到OUTPUT.TXT文件中。输出文件仅包含一个数,为所求的最少的经费。

16.[问题描述]:Sramoc(K,M)表示用数字0、1、2…、K-1组成的自然数中能被M整除的最小数。给定 K、M,求Sramoc(K,M)。例如 K=2,M=7的时候,Sramoc(2,7)= 1001。

[输入格式]:

从文件SRAMOC.DAT读入数据。第一行为两个整数K、M满足2<=K<=10、1<=M<=1000。

[输出格式]:

输出Sramoc(K,M)到 SRAMOC.OUT。

[样例]:

SRAMOC.DAT:

2 7

SRAMOC.OUT: