动态规划步骤

动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。

根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下：

1标准动态规划的基本框架

1.对fn+1(xn+1)初始化;{边界条件}

2.fork:=ndownto1do

3.for每一个xk∈Xkdo

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

end;

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

10.for每一个x1∈X1do

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

12.输出t;2但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个

步骤进行：

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

2.递归地定义最优值。

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

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

步骤(1)--(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)

可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤

(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的

信息，快速地构造出一个最优解。3城市街道问题：456【例题4】合唱队形【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…<Ti,Ti>Ti+1>…>TK(1≤i≤K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件chorus.in的第一行是一个整数N（2≤N≤100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8186186150200160130197220【样例输出】4【数据规模】对于50%的数据，保证有n≤20；对于全部的数据，保证有n≤100。7【算法分析】我们按照由左而右和由右而左的顺序，将n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设a为身高序列，其中a[i]为同学i的身高；b为由左而右身高递增的人数序列，其中b[i]为同学1‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然b[i]={b[j]|同学j的身高<同学i的身高}+1；c为由右而左身高递增的人数序列，其中c[i]为同学n‥同学i间（包括同学i）身高满足递增顺序的最多人数。显然c[i]={c[j]|同学j的身高<同学i的身高}+1；由上述状态转移方程可知，计算合唱队形的问题具备了最优子结构性质(要使b[i]和c[i]最大，子问题的解b[j]和c[k]必须最大(1≤j≤i-1，i+1≤k≤n))和重迭子问题的性质(为求得b[i]和c[i]，必须一一查阅子问题的解b[1]‥b[i-1]和c[i+1]‥c[n])，因此可采用动态程序设计的方法求解。显然，合唱队的人数为(公式中同学i被重复计算，因此减1)，n减去合唱队人数即为解。8出列人数最少，也就是说留的人最多，也就是序列最长。这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于，包括他在内向左求最长上升子序列，向右求最长下降子序列。我们看一下复杂度：计算最长下降子序列的复杂度是O（N2），一共求N次，总复杂度是O（N3）。这样的复杂度对于这个题的数据范围来说是可以AC的。但有没有更好的方法呢？其实最长子序列只要一次就可以了。因为最长下降（上升）子序列不受中间人的影响。只要用OPT1求一次最长上升子序列，OPT2求一次最长下降子序列。这样答案就是N-max(opt1[i]+opt2[i]-1).复杂度由O（N3）降到了O（N2）。【算法分析】9【问题描述】PALMIA国家被一条河流分成南北两岸，南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线相交（如果相交，则很可能导致碰船）。你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。船

10【输入文件】ships.in输入文件由几组数据组成。每组数据的第一行有2个整数X，Y，中间有一个空格隔开，X代表PALMIA河的长度（10<=X<=6000），Y代表河的宽度（10<=Y<=100）。第二行包含整数N，表示分别坐落在南北两岸上的村庄的数目（1<=N<=5000）。在接下来的N行中，每一行有两个非负整数C，D，由一个空格隔开，分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离（C代表北岸的村庄，D代表南岸的村庄），不存在同岸又同位置的村庄。最后一组数据的下面仅有一行，是两个0，也被一空格隔开。【输出文件】ships.out对输入文件的每一组数据，输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。【输入样例】30472242610315129817174200【输出样例】411【问题分析】这道题目相对来说思考难度较高，从字面意义上看不出问题的本质来，有点无法下手的感觉。寻找规律自然要推几组数据，首先当然有从样例入手；仔细观察上图：红色航线是合法的，那么他们满足什么规律呢？C1

C2

C3

C4北岸红线的端点：4

9

15

17南岸红线的端点：2

8

12

17D1

D2

D3

D4不难看出无论线的斜率如何，都有这样的规律：C1<C2<C3<C4且

D1<D2<D3<D412如果我们把输入数据排升序，问题变抽象为：在一个序列（D）里找到最长的序列满足DI<DJ<Dk……且i<j<k这样的话便是典型的最长非降子序列问题了。。。。法二：边界条件法边界法其实就是把数据往小了缩，显然N=1是答案是1。N=2时呢？考虑这样一组数据：N=2C1

D1C2

D2当C1<C2时，如果D1>D2那么一定会相交，反之则不会相交。当C1

>C2时，如果D1<D2那么一定会相交，反之则不会相交。N=3C1

D1C2

D2C3

D3……其实不用在推导N=3了，有兴趣的可以推导去。看N=2时就能得出：对于任意两条航线如果满足Ci<Cj且Di<Dj则两条航线不相交。这样的话要想在一个序列里让所有的航线都不相交那比然满足，C1<C2<C3…Cans且D1<D2<D3…<Dans，也就是将C排序后求出最长的满足这个条件的序列的长度就是解。这样分析后显然是一个最长非降子序列问题。复杂度：排序可以用O（nlogn）的算法，求最长非降子序列时间复杂度是O(n2).总复杂度为O（n2）.13背包问题0/1背包【问题描述】一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。【输入格式】第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；第2..N+1行：每行二个整数Wi,Ci，表示每个物品的重量和价值。【输出格式】仅一行，一个数，表示最大总价值。【样例输入】package.in10421334579【样例输出】package.out1214【解法一】【算法分析】设f(i，x)表示前i件物品，总重量不超过x的最优价值，则f(i，x)=max(f(i-1，x-w[i])+c[i],f(i-1，x）)；f（n，m）即为最优解。下面例出F[I，X]的值，I表示前I件物品，X表示重量【参考程序】(顺推法)programpackage;constmaxm=200;maxn=30;varm,n,x,i:integer;c,w:array[1..maxn]ofinteger;f:array[0..maxn,0..maxm]ofinteger;functionmax(x,y:integer):integer;//求x和y最大值beginifx>ythenmax:=xelsemax:=y;end;15BEGINassign(input,'package.in');assign(output,'package.out');reset(input);rewrite(output);readln(m,n);//背包容量m和物品数量nfori:=1tondoreadln(w[i],c[i]);//每个物品的重量和价值fori:=1tondoforx:=1tomdobegin//f(i，x)表示前i件物品，总重量不超过x的最优价值ifx>=w[i]thenf[i,x]:=max(f[i-1,x-w[i]]+c[i],f[i-1,x])elsef[i,x]:=f[i-1,x];end;writeln(f[n,m]);//f(n，m)为最优解close(input);close(output);END.使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组。16【解法二】【算法分析】本问题的数学模型如下：设f(x)表示重量不超过x公斤的最大价值，则f(x)=max{f(x-w[i])+c[i]}

当x>=w[i]，1<=i<=n。下面例出F[x]表示重量不超过x公斤的最大价值，x表示重量F[x]F[1]F[2]F[3]F[4]F[5]F[6]F[7]F[8]F[9]F[10]I=10111111111I=20133444444I=30135568899I=401355699101217【参考程序】programstar_package;Vari,x,k,n,m:longint;f:array[0..100000]oflongint;w,c:array[0..2000]oflongint;beginassign(input,'package.in');assign(output,'package.out');reset(input);rewrite(output);fillchar(f,sizeof(f),0);readln(m,n);//背包容量m和物品数量nfori:=1tondoreadln(w[i],c