动态规划算法.doc

动态规划
（一）、动态规划的基本思想：
    动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
二、设计动态规划法的步骤：
1、找出最优解的性质，并刻画其结构特征；
2、递归地定义最优值（写出动态规划方程）；
3、以自底向上的方式计算出最优值；
4、根据计算最优值时得到的信息，构造一个最优解。
步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。
三、动态规划问题的特征：
动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。
（二）、动态规划算法的基本步骤
设计一个标准的动态规划算法，通常可按以下几个步骤进行：
3. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。
4. 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
5. 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。
6. 写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。
动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：
标准动态规划的基本框架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):=t; {计算fk(xk)的最优值}
end;
9. t:=一个极值; {∞或－∞}
10. for 每一个x1∈X1 do
11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}
12. 输出t;
但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行：
2. 分析最优解的性质，并刻划其结构特征。
3. 递归地定义最优值。
4. 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
5. 根据计算最优值时得到的信息，构造一个最优解。
步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。
<!-- #EndEditable -->
（三）、动态规划概述
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，我们知道，最短路径是AB1C2D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：AB1C2是A到C2的最短路径，B1C2D也是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(<=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;
<I>var</I>
    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;
<I>var</I>
    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;<I>var</I> l:point);
<I>var</I>
   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);
<I>var</I>
   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 < sum[x1,y1]) or (sum[x1,y1]=-1) then 
                         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;
<I>var</I>
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
0
初看这道题,很容易便可以想到动态规划,因为第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;
<I>var</I>
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]<a[i,j])) {判断比当前解优}
then a[i,j]:=a[i-1,l]+c[l,j].t[(i-1) mod c[l,j].num+1]; {赋值}
end;
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. m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的最后一本书的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的人抄书页数尽可能少. (GDOI''99 Books).
2. 有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。　（GDKOI'2000 Compress)
3. Canada境内有自西向东的一系列城市：Halifax,Hamilton,Montelia,Vancouver...，各个城市之间可能有航班相连，也可能没有，现要求从最西的城市出发，自西向东到达最东的城市，再返回最西的城市，除最西城市外，其他每个城市只能访问一次，求最多能访问多少个城市．
（七）习题
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 │    │输出文件：div．out　│
├─────────┤　　├──────────┤
│2 　　　　　　　　│　     │Divisible           │
│4 7                         │　　│Not Divisible　　　 │
│17 5 -21 15 　　　│　　│　　　　　　　　　　│
│4 5　　　　 　　　│　　│　　　　　　　　　　│
│17 5 -21 15 　　　│　　│　　　　　　　　　　│
└─────────┘　　└──────────┘
2.背包问题
设有ｎ种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限