动态规划幻灯片-king

动态规划（DP）在分治算法中，为了解决一个大问题，我们总是将它分解成两个或更多的小问题，然后分别解决每个小问题，再把各小问题的解答组合起来就得到原来问题的借。小问题通常和原问题本质相似，只是规模小些，一般都可以用递归的方法来解决，如汉诺塔问题和快速排序都是例子。有些问题当把问题分解成子问题，使之能够从这些子问题的借得到原问题的解时，子问题的数目太多，如果把每个子问题再分解，必将得到更多的子问题，以至于最后解决问题需要耗费指数级的时间。其实，在这类问题中，子问动态规划-king的数目只是多项式个，于是在上述算法中，一定有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时简单查一下，这样我们可以避免大量的重复计算为了实现上述方法，我们用一个数组记录所有已解决的子问题的答案，无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组中，这种方法在程序设计中被称为动态规划（DP）动态规划-king动态规划简介

动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年，美国数学家贝尔曼（R.Bellman）提出了解决这类问题的“最优化原则”，1957年发表了他的名著《动态规划》，该书是动态规划方面的第一本著作。动态规划问世以来，在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用，取得了显著的效果。

动态规划-king动态规划简介动态规划运用于信息学竞赛是在90年代初期，它以独特的优点获得了出题者的青睐。此后，它就成为了信息学竞赛中必不可少的一个重要方法，几乎在所有的国内和国际信息学竞赛中，都至少有一道动态规划的题目。所以，掌握好动态规划，是非常重要的。

动态规划-king动态规划简介动态规划是一种方法，是考虑问题的一种途径，而不是一种算法。因此，它不像深度优先和广度优先那样可以提供一套模式。它必须对具体问题进行具体分析。需要丰富的想象力和创造力去建立模型求解。

动态规划-king动态规划思路：用一个数组来记录所有已解决的子问题的答案。无论子问题以后是否被用到，只要它被计算过，就将其结果存入数组中，这种方法在程序设计中被称为动态规划。相比较分治算法，提高了程序效率。动态规划-king最短路径问题如图表示从起点A到终点E之间各点的距离。求A到E的最短路径。

动态规划-king以上求从A到E的最短路径问题，可以转化为三个性质完全相同，但规模较小的子问题，即分别从B1、B2、B3到E的最短路径问题。记从Bi(i=1,2,3)到E的最短路径为S(Bi)，则从A到E的最短距离S(A)可以表示为：

动态规划-king同样，计算S(B1)又可以归结为性质完全相同，但规模更小的问题，即分别求C1，C2，C3到E的最短路径问题S(Ci)(i=1,2,3)，而求S(Ci)又可以归结为求S(D1)和S(D2)这两个子问题。从图1.1.1可以看出，在这个问题中，S(D1)和S(D2)是已知的，它们分别是： S(D1)=5，S(D2)=2动态规划-king因而，可以从这两个值开始，逆向递归计算S(A)的值。计算过程如下：

动态规划-king即

S(C1)=8 且如果到达C1，则下一站应到达D1； S(C2)=7 且如果到达C2，则下一站应到达D2； S(C3)=12 且如果到达C3，则下一站应到达D2；动态规划-king即

S(B1)=20 且如果到达B1，则下一站应到达C1； S(B2)=14 且如果到达B2，则下一站应到达C1； S(B3)=19 且如果到达B3，则下一站应到达C2；

动态规划-king动态规划-king图的邻接矩阵如下：0251-1-1-1-1-1-1

-10-1-11214-1-1-1-1

-1-10-16104-1-1-1

-1-1-10131211-1-1-1

-1-1-1-10-1-139-1

-1-1-1-1-10-165-1

-1-1-1-1-1-10-110-1

-1-1-1-1-1-1-10-15

-1-1-1-1-1-1-1-102

-1-1-1-1-1-1-1-1-10采用逆推法设f（x）表示点x到v10的最短路径长度则f(10)=0

f(x)=min{f(i)+a[x，i]当a[x，i]>0,x<i<=n}动态规划-king如何记录路径：１记录数字标志；２顺序或递归实现vari,j,k,m,n:longint;weight,cost:array[1..1000]oflongint;f,ff:array[0..1000,0..1000]oflongint;procedureos(i,j:longint);beginif(i=0)or(j=0)thenexit;caseff[i,j]of1:os(i-1,j);2:beginos(i-1,j-weight[i]);write(i,'');end;end;end;beginassign(input,'bag01.in');reset(input);//bag012.outassign(output,'bag01.out');rewrite(output);readln(m,n);fori:=1tondoread(weight[i]);readln;fori:=1tondoread(cost[i]);readln;fillchar(f,sizeof(f),0);fori:=1tomdof[0,i]:=0;fori:=1tondof[i,0]:=0;fori:=1tondoforj:=mdownto1dobeginifj-weight[i]>=0thenbeginiff[i-1,j]>f[i-1,j-weight[i]]+cost[i]thenbeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endelsebeginf[i,j]:=f[i-1,j-weight[i]]+cost[i];ff[i,j]:=2;endendelsebeginf[i,j]:=f[i-1,j];ff[i,j]:=1;endend;writeln(f[n,m]);os(n,m);close(input);close(output);end.

k:=0;fori:=ndownto1doforj:=1tomdoif(ff[i,j]=1)and(f[i,j]=max)thenbegininc(k);p[k]:=i;max:=max-c[i];break;end;fori:=kdownto2dowrite(p[i],'');write(p[1]);动态规划-king数字三角形（IOI’94）如下所示一个数字三角形738810274445265写一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字和最大每一步可沿直向下或右斜线向下走1<三角形行数<=100三角形中的数字为整数0，1，，，99动态规划-king数字三角形（IOI’94）输入：第一行为一个自然数，表示数字三角形的行数n，接下来的n行表示一个数字三角形输出：一行一个整数表示最大和5738810274445265输出：30动态规划-king分析假设从顶至数字三角形的某一位置的所有路径中，所经过的数字总和最大的那条路径我们称之为该位置的最大路径，由于问题规定每一步只能沿直线或右斜线向下走，若要走过某一位置，则其前一位置必为其正上方或左上方两个位置之一。由此可知，当前位置的最优路径必定与其左上方或正上方两个位置的最优路径有关，且来自其中最优的一个我们用一个两维数组a记录三角形中的数a[I,j]表示数字三角形的第I行第j列的数，再用一个两维数组maxsum记录每个位置的最优路径的数字和。计算maxsum数组可以用逐行递推的方法实现（像杨辉三角）动态规划-king分析按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。先求出第n-1阶段(第n-1行上各点)到第n行的的最大和，再依次求出第n-2阶段、第n-3阶段……第1阶段(起始点)各决策点至第n行的最佳路径。

设：f[i,j]为从第i阶段中的点j至第n行的最大的数字和；

则:f[n,j]=a[n,j]

1<=j<=n

f[i,j]=max{a[i,j]+f[i+1,j],a[i,j]+f[i+1,j+1]}

1<=j<=i.

f[1,1]即为所求。动态规划-king动态规划的基本思想最优子结构用动态程序设计方法来解决一个问题的第一步是规划一个最优解的结构。我们说一个问题具有最优子结构性质，如果该问题的最优解中包含了一个或多个子问题的最优解，当一个问题呈现出最优子结构时，动态程序设计可能就是一个合适的候选方法了。动态规划-king动态规划的基本思想如数字三角形就有最优子结构当前位置的最优路径必定与其左上方或正上方的两个位置的最优路径有关，且来自其中最优的一个，即问题的最优解包含了其中一个子问题的最优解如果将问题稍微改变：将三角形中的数字改为-100~100之间的整数，计算从顶至底的某处的一条路径，使路径经过的数字综合最接近零，这个问题就不具备最优子结构性质，因为子问题最优反而可能造成问题的解原离零动态规划-king动态规划的基本思想重叠子问题子问题的空间要较小，也就是用来解原问题的一个递归算法可反复解同样的子问题，而不是总是产生新的子问题，即子问题的总数是问题规模的一个多项式。当一个递归算法不断地遇到同一问题时，我们说该最优化问题包含有重叠子问题相反地，使用分治法解决的问题往往在递归的每一步都产生出全新的问题来，如快速排序算法。动态总是充分使用重叠子问题，对每个子问题只解一次，把解放在一个数组中，需要时查看。动态规划-king动态规划的基本思想无后效性“过去的历史只能通过当前状态去影响它未来的发展，当前的状态是对以往历史的一个总结”，这种特性称为无后效性，是多阶段决策最优化问题的特征。

动态规划-king想要掌握好动态规划，首先要明白几个概念：阶段、状态、决策、策略、指标函数。

1．阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量。

2．状态：状态表示每个阶段开始所处的自然状况和客观条件，它描述了研究问题过程中的状况，又称不可控因素。

3．决策：决策表示当过程处于某一阶段的某个状态时，可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策，在最优控制中也称为控制。描述决策的变量，称为决策变量。

4．策略：由所有阶段的决策组成的决策函数序列称为全过程策略，简称策略。

5．状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程。

6．指标函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数。指标函数的最优值，称为最优值函数。

动态规划-king动态规划算法的基本步骤如果碰到一个问题，能够满足以上两个条件的话，那么就可以去进一步考虑如何去设计使用动态规划：

（1）划分阶段。把一个问题划分成为许多阶段来思考

（2）设计合适的状态变量(用以递推的角度)

（3）建立状态转移方程(递推公式)

（4）寻找边界条件(已知的起始条件)

如果以上几个步骤都成功完成的话，我们就可以进行编程了。

动态规划-king最长不下降子序列设有由n个不相同的整数组成的数列，记为:

a(1)、a(2)、……、a(n)且a(i)<>a(j)

(i<>j)

例如3，18，7，14，10，12，23，41，16，24。

若存在i1<i2<i3<…<ie且有a(i1)<a(i2)<…<a(ie)则称为长度为e的不下降序列。如上例中3，18，23，24就是一个长度为4的不下降序列，同时也有3，7，10，12，16，24长度为6的不下降序列。程序要求，当原数列给出之后，求出最长的不下降序列。

动态规划-king算法分析根据动态规划的原理，由后往前进行搜索。

1·对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的不下降序列；

2·若从a(n-1)开始查找，则存在下面的两种可能性：

①若a(n-1)<a(n)则存在长度为2的不下降序列a(n-1)，a(n)。

②若a(n-1)>a(n)则存在长度为1的不下降序列a(n-1)或a(n)。

3·

一般若从a(i)开始，此时最长不下降序列应该按下列方法求出:

在a(i+1),a(i+2),…,a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。4.用数组b(i),c(i)分别记录点i到n的最长的不降子序列的长度和点i后继节点的编号状态转移方程：f(i)=max{f(j)+1}1<=j<I,b[j]<b[i]动态规划-king最长不下降序列拓展一求序列中最长不下降序列的个数设t(i)为前i个数中最长不下降序列的个数,则t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)+1)初始为t(i)=1当f(i)=n时，将t(i)累加举例：1234658109

f:123455677t:111111222答案：f=7时，边界为∑t=4动态规划-king最长不下降序列拓展二求本质不同的最长不下降序列个数有多少个？如：1234658109有，12346810,12345810,1234689,1234589都是本质不同的。但对于1223354

f1223344t1112244

答案有8个，其中4个1235，4个1234t(i)=∑t(j)(1<=j<i<=m,bj<bi,f(i)=f(j)+1，bj<>bk,1<=k<j)动态规划-king最长公共子序列一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=<x1,x2….xm>,则另一序列Z=<z1,z2,….zk>是X的子序列是指存在一个严格递增的下标序列<i1,i2,….ik>,使得对于所有j=1,2,….k有：

Xij=Zj动态规划-king例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>则序列<B,C,A>是X和Y的一个公共子序列。序列<B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列动态规划-king给定两个序列X=<x1,x2,….xm>和Y=<y1,y2,…yn>,要求找出X和Y的一个最长公共子序列输入：输入文件共有两行，每行为一个由大写字母构成的长度不超过200的字符串。表示序列X和Y。输出输出文件第一行为一个非负整数，表示所求得的最长公共子序列的长度，若不存在公共子序列，则输出文件仅有一行输出一个整数0，否则在输出文件的第二行输出所求得的最长公共子序列（也用一个大写字母组成的字符串表示），若符合条件的最长公共子序列不止一个，只需要输出其中任意一个。动态规划-king样例输入

ABCBDABBDCABA样例输出4

BCBA动态规划-kingC[I,j]=0当I=0或j=0C[I-1,j-1]+1当I,j>=且xi=yjMax(c[I-1,j],c[I,j-1])当I,j>0且xi<>yj动态规划-king若输出所有公共子序列呢？右边方法的效率不高，但可以实现。只输出一个公共序列：procedurelcs(i,j:longint);beginif(i=0)or(j=0)thenexit;ifd[i,j]=1thenbeginlcs(i-1,j-1);write(a[i],'');endelseifd[i,j]=2thenlcs(i-1,j)elselcs(i,j-1);end;procedureprint;vari,j,k:longint;flag:boolean;begingt[p]:='';fori:=1tomaxdogt[p]:=gt[p]+gg[i];flag:=true;fori:=1top-1doifgt[p]=gt[i]thenbeginflag:=false;break;end;ifflagtheninc(p);end;procedurelcs(k,i,j:longint);beginifk=0thenbeginprint;exit;end;if(i=0)or(j=0)thenbeginexit;end;ifd[i,j]=1thenbegingg[k]:=a[i];lcs(k-1,i-1,j-1);endelseifd[i,j]=2thenlcs(k,i-1,j)elseifd[i,j]=3thenlcs(k,i,j-1)elseifd[i,j]=4thenbeginlcs(k,i-1,j);lcs(k,i,j-1);end;end;动态规划-king拦截导弹（p1078）某国为了防御敌国的导弹袭击，发明出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

动态规划-king拦截导弹输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入：38920715530029917015865

输出：6（最多拦截的导弹）2（最小需要配备的系统）动态规划-king拦截导弹阶段i：由右而左计算导弹n‥导弹1中可拦截的最多导弹数（1≤i≤n）；状态B[i]：由于每个阶段中仅一个状态，因此可通过一重循环fori:=n-1downto1do枚举每个阶段的状态B[i]；决策k：在拦截导弹i之后应拦截哪一枚导弹可使得B[i]最大（i+1≤k≤n），动态规划-king算法：这道题就是典型的最长单调序列和最长单调序列的覆盖问题，两个问题分别求。问题一：求最长单调序列的长度。我们设opt[i]表示从A1到Ai的最长单调序列长度，则：opt[1]=1opt[i]=max{opt[k]+1}(1<=k<i)&(Ak>=Ai)最后输出opt[n].问题二：最长单调序列的覆盖个数我们可以不断求出最长单调序列，把它们从序列集合中删去，直到集合为空集，在此过程中进行累加。复杂度：方法的时间复杂度为o(n^2)，tju1004已经可以Accepted，但是如果n>1000000时，速度显然不如人意。动态规划-king改进：有没有更好的方法呢？当然有！最长单调序列，顾名思义，单调的，即：A[k]<=(or>=><)A[i](k<i)于是难道不可以只保存最后一个数？首先,开一个足够大的数组A:array[1..maxn]oflongintA[i]表示长度为i的最长单调序列的最后一个数字，程序如下：动态规划-kingproceduremain;var.............beginfillchar(a,sizeof(a),0);ans:=0;{最长单调序列的长}readln(n);fors:=1tondobeginread(x);l:=1;r:=ans;{左、右范围}whliel<=rdobegin{二分}m:=(l+r)shr1;ifa[m]<=xthenl:=m+1elser:=m-1;end;ifl>anstheninc(ans);{新建，即长度为ans+1的最长单调序列出现了！}a[l]:=x;end;end;最长单调序列的覆盖个数也很好求，只要将ifa[m]>=xthenl:=m+1elser:=m-1中的<=转换为>=即可，其它类似。算法的复杂度显然降低了！动态规划-king合唱队形

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，

则他们的身高满足T1<...<Ti>Ti+1>…>TK(1<=i<=K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

动态规划-king输入文件

输入文件chorus.in的第一行是一个整数N(2<=N<=100)，表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti(130<=Ti<=230)是第i位同学的身高(厘米)。

-输出文件

输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

-样例输入

8

186186150200160130197220

-样例输出

4

动态规划-king从左到右进行最长不下降子序列从右到左进行最长不上升子序列然后综合考虑，枚举二者最大值动态规划-king方格取数（P1205）设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：动态规划-king方格取数某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

输入

输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。

输出

只需输出一个整数，表示2条路径上取得的最大的和。动态规划-king方格取数动态规划-king若只考虑走一次的情况，则是一个标准的动态规划的过程。

根据走的步数来分阶段

阶段：阶段1，在位置(1,1)，阶段2，位置可能有两个(1,2)，(2,1)，等。其中的规律是阶段k，可能的位置是(x,k+1-x),(k>=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)中的数。动态规划-king现考虑走两次。

题目中是两次分开走的，但我们可以看成两个人同时走。这时依然按照行走的步数来分类。

这样的情况下有一个不同的情况是：可能两个人同时走入同一个格子取数，这时肯定不能取两次数。

两条路线同时进行的动态规划中，状态和决策以及状态转方程移要复杂一些。动态规划-king两条路线同时进行的动态规划

阶段：按所走的步数来分阶段，从左上角走到右下角，共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。故可只用ｘ坐标来表示一点的坐标，故状态可表示为(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(1,1,1)＝map(x1,1+1-x1)即map(1,1)

f(k,x1,x2)=max{f(k-1,x1',x2')+map(x1,y1)｜x1=x2，

f(k-1,x1',x2')+map(x1,y1)＋map(x2,y2)｜x1<>x2}

(x1',x2')表示可通过某决策到达(x1,x2)的所有点动态规划-king记忆化搜索方式解决动规functionfind(i,x1,x2:longint):longint;varg,h,t1:longint;beginif(i=1)and(x1=1)and(x2=1)thenbeginf[1,1,1]:=map[1,1];find:=f[1,1,1];vis[1,1,1]:=false;exit;end;if(x1=0)or(x2=0)or(i+1-x1=0)or(i+1-x2=0)thenbeginfind:=f[i,x1,x2];exit;end;ifnotvis[i,x1,x2]thenbeginfind:=f[i,x1,x2];exit;end;t1:=0;ifx1=x2thenbeginforg:=0to1doforh:=0to1dobeginift1<find(i-1,x1-g,x2-h)+map[x1,i+1-x1]thent1:=find(i-1,x1-g,x2-h)+map[x1,i+1-x1];end;endelsebeginforg:=0to1doforh:=0to1doift1<find(i-1,x1-g,x2-h)+map[x1,i+1-x1]+map[x2,i+1-x2]thent1:=find(i-1,x1-g,x2-h)+map[x1,i+1-x1]+map[x2,i+1-x2];end;f[i,x1,x2]:=t1;find:=t1;vis[i,x1,x2]:=false;end;动态规划-king数字最大乘积在数字串中插入若干(K个)乘号使总的乘积最大。分析：定义从l到r加入k个乘号的最大乘积值为p(l,r,k)。动态规划-king解题思路

定义:从l到r加入k个乘号的最大乘积值p(l,r,k)。p(l,r,k)=max{d(l,q)*p(q+1,r,k-1)}动态规划-king机器生产某工厂购进1000台机器，准备生产P1和P2两种产品。若生产产品P1，每台机器每年可收入4500元，但机器损坏率达65%。若生产产品P2，每台机器每年可收入3500元，但损坏率仅有35%。三年后机器全部淘汰，购入新机器。应该如何安排生产（计划以一年为周期），使三年收入最多？动态规划-king分析：假设X1、Y1表示第一年时生产P1的机器台数和生产P2的机器台数，则X2，Y2，X3，Y3以此类推。可知：

X1+Y1=1000 X2+Y2=0.35*X1+0.65*Y1 X3+Y3=0.35*X2+0.65*Y2而三年的总收入为：Z=4500*（X1+X2+X3）+3500*（Y1+Y2+Y3）（1）设在第二年后还剩N台机器，则第三年的收入为：

Z(3,N) =4500*X3+3500*Y3 =4500*X3+3500*（N-X3） =1000*X3+3500N

显然我们知道：0<=X3<=N，则Z3最大时，X3=N（Y3=0），此时，Zmax(3，N)=4500*N。（2）设在第一年后还剩N台机器，则第二年后（最后两年）的收入为：

Z（2，N）=4500*X2+3500*（N-X2）+Zmax(3,0.35*X2+0.65*(N-X2)) =1000*X2+3500*N+4500*（0.65*N-0.3*X2） =（3500+2925）*N-（1350-1000）*X2 <=6425*N

显然，当X2=0，X3=0.65*N时，Z（2，N）取最大值

动态规划-king（3）最后考虑整个三年的生产，设开始时有N台机器，则三年的收入总和为：

Z（1，N）=4500*X1+3500（N-X1）+Zmax(2，0.35*X1+0.65*(N-X1)) =1000*X1+3500*N+6425*（0.65*N-0.3*X1） =（3500+6425*0.65）*N-（0.3*6425-1000）*X1 <=（3500+6425*0.65）*N

综上所述，当X1=0，X2=0，X3=0.65*0.65*N时，收入取得最大值。即： 生产P1的机器台数 生产P2的机器台数第1年 0 1000第2年 0 650第3年 422 0此时三年收入最大。动态规划-kingMOD4余数最小问题如图，已知一个有向图，求一条从最左边的点走到最右边点的方案（只能从左往右走），使得所经过的权值和除以4的余数最小。动态规划-king

设所有点从左至右编号为1…4，MIN（i）表示前I个点的最优值，很容易得出一个方程：

Min(i)=min{(Min(I-1)+num[I-1,1])mod4,Min(I-1)+num[I-1,2])mod4}

通过这个方程可以求出一条路径为（2+3+1）MOD4=2但最优值实际上是（2+1+1）MOD4=0。

为什么会出错呢？分析动态规划-king

观察以上数据发现取Min(３)的时候，动态规划求出来的最优值为１，而正确的值应该为0，由此可知本题对应于一条最优路径，并不是这条路径上的所有点的最优值都是从点１到该点可得的最优值，对于每一个阶段都取最优值并不能保证求出最优解，即不满足最优化原理，因此这种规划方法在本题行不通。动态规划-king让我们来换一个思路思考本题，因为本题是要求总和除以４余数最小的一条路径，我们先撇开最小余数不去管它，而是将本题改为从点1到点４的所有路径中，求出每条路上权值和除以４的不同余数的个数。我们设一个数组can[I,j]表示从点1至点Ｉ可不可以求出一条路径是该路径的权值总和除以４的余数为Ｊ，那么又可以得出一个方程：

can[I,j]:=can[I-1,k]and((k+num[I,p])mod4=j)(0<=k<=3,1<=p<=2)can[1,0]=truecan[1,1]=falsecan[1,2]=falsecan[1,3]=false

通过这个方程我们可以求出从点1至点Ｉ可以达到的所有余数，我们只要从这些余数中选出一个值最小的输出就行。动态规划-king线性规划模型

例1：机器分配问题。总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=150，N<=100。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个N*M的矩阵，表明了第I个公司分配J台机器的盈利。

动态规划-king分析用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1<=I<=N,1<=J<=M,0<=K<=J)初始值:F(0,0)=0时间复杂度O(N*M2)动态规划-king有一条河从东向西将某地区分为南北2个部分。河的两岸各有N个城市。北岸的每个城市都与南岸的某个城市是友好城市，而且关系是一一对应的。现在要求在2个友好城市之间建立一条航线，但由于天气的缘故，所有的航线都不能相交，因此，就不能给所有的友好城市建立友好航线。请设计一个修建航线的方案，能建最多的航线而且不相交。输入：第一行为一个正整数N(N<=1000)以下N行，记第i行有一个正整数j，表示北岸的城市i与南岸的城市j互为友好城市。其中城市编号是按从东到西排列的。输出：仅一行，即最多的航线数。

船(ceoi)动态规划-king

首先我们需要判定对于给定的两条航线是否相交，设北岸城市i1，j1(i1<j1)分别与南岸城市i2，j2互为友好城市，那么这两条航线不相交(以下简称为i1，j1相容)的充要条件是I2<=J2。(结论1)由下图就可以很容易地得到这个结论。

i1j2i2j1j2i2j1i1北岸：

南岸：

图

一

图

二

分析动态规划-king

从上面的结论可以看出，最优的选择方案中，如果将所有航线按北岸村庄号从小到大排序，序列中每一个北岸村庄对应的南岸村庄号必然满足B1<B2<B3……<Bn（n为选出来的航线数）。同样，对于任一个方案，如果北岸村庄排好序后，与之对应的南岸村庄也是按升序排列，那么该方案必然不存在相交的两条航线；相反，如果南岸村庄不是按升序排列，必存在两条相交的航线。因此，我们可以先将各航线按北岸村庄号排一个序，那么最优的方案必然是从相对应的南岸村庄中找出一个最长不下降序列，该序列的长度即为问题的解。动态规划-king凸多边形三角划分

给定一个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数N

第二行N个顶点（从1到N）的权值输出格式：最小的和的值各三角形组成的方式输入示例：5122123245231输出示例：Theminimumis：12214884Theformationof3triangle:345,153,123动态规划-king分析设F[I,J]（I<J）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0<I<K<J<=N)初始条件:F[1，2]=0目标状态:F[1,N]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算

动态规划-king动态规划-king堆塔问题

设有n个边长为1的正立方体，在一个宽为1的轨道上堆塔，但塔本身不能分离。

例如n=1时，只有1种方案□

n=2时，有2种方案

堆塔的规则为底层必须有支撑，如下列的堆法是合法的：

下面的堆法是不合法的：

程序要求：输入n(n<=40)，求出

动态规划-king程序要求：输入n(n<=40)，求出

①总共有多少种不同的方案

②堆成每层的方案数是多少，例如n=6时，堆成1层的方案数为1，……堆成6层的方案数为1……

动态规划-king分析问题①的分析不再重复

关于问题②，可以这样考虑，将n个立方体的第一列去掉的话，则成为一个比n小的堆塔问题，这样问题②就可以用动态规划法来解。具体方法是从1到n依次求出堆成每层的方案数，设f(n,k)为堆成k层的方案数，则递推公式为：

[算法设计]

由于n最大可达到40，所以堆塔的总方案数超过了长整形数的范围，程序采用了高精度加法运算。

动态规划-king矩阵乘法一个a*b的矩阵和一个b*c的矩阵相乘需要a*b*c次乘法，得到一个a*c的矩阵。现在给你一系列矩阵的连乘式，求最少的乘法次数。子结构划分：中分。考虑最后两个矩阵相乘。这两个矩阵必定对应某一个划分，由左右两部分分别计算得到。最优子结构？无后效性？动态规划-king动态规划方程变量的定义：ri::=第i个矩阵的行数ci::=第i个矩阵的列数fij::=将第i-j个矩阵相乘所需的最少乘法次数方程：fij=min{fik+fk+1j}+ri*ck*cji<=k<=jfii=0Answer=f1n动态规划-king取数游戏有n个数a1、a2、…、an。每次从中删去一个数，规定最左最右两个数不能删除。这样共进行n-2次，求得分最高的方案。计分方式：设某一次删除的数为ai，则你的得分为ai-1*ai*ai+1。所有得分相加即为最后总分。动态规划-king动态规划方程变量的定义：fij::=第i-j个数所能得到的最高得分方程：fij=max{fik+fkj}+ai*ak*aj1<=i<k<j<=Nfii+1=0Answer=f1n动态规划-king01背包问题一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

动态规划-king分析显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数设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（0，x）＝0

，f(i,0)=0;动态规划-king完全背包问题设有n种物品，每一种物品数量无限。第i种物品每件重量为wi公斤，每件价值ci元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。

动态规划-king问题分析动态规划-king排队买票问题一场演唱会即将举行。现有n个歌迷排队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第i位歌迷买一张票需要时间Ti（1≤i≤n），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，假如Rj〈Tj+Tj+1，这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程。现给出n,Tj和Rj，求使每个人都买到票的最短时间和方法。动态规划-king最优子结构性质:在最优策略中，任意m个连续的决策也肯定是最优的,即问题的最优解包含子问题的最优解。无后效性：要使前i个人买票时间最短，只需考虑前i个人的买票方式，与队列以后的人无关。

动态规划-king递归方程令f[i]表示到第i个人为止所需的最短时间，则数据结构用一个数组f[]表示到第i个人为止所需的最短时间源代码

动态规划-king程序实现BUY-TICKS(T,R)

n←length[T]f[0]←0

f[1]←T[1]forl←2ton

do

f[i]←f[i-2]+R[i-1]iff[i]

>f[i-1]+T[i]thenf[i]←f[i-1]+T[i]returnf动态规划-king机器分配

总公司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M<=15，N<=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。

动态规划-king分析用机器数来做状态，数组F[I，J]表示前I个公司分配J台机器的最大盈利。则状态转移方程为:F[I，J]=Max{F[I-1，K]+Value[I，J-K]}(1<=I<=N,1<=J<=M,0<=K<=J)初始值:F(0,0)=0时间复杂度O(N*M2)动态规划-king凸多边形三角划分

给定一个具有N（N<50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数N

第二行N个顶点（从1到N）的权值输出格式：最小的和的值各三角形组成的方式输入示例：5122123245231输出示例：Theminimumis：12214884Theformationof3triangle:345,153,123动态规划-king分析设F[I,J]（I<J）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0<I<K<J<=N)初始条件:F[1，2]=0目标状态:F[1,N]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算

动态规划-king系统可靠性

一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。

输入文件格式：第一行：nC第二行：C1P1(0)P1(1)…P1(X1)（0<=X1<=[C/Ck]）…第n行：CnPn(0)Pn(1)…Pn(Xn)（0<=Xn<=[C/Cn]）动态规划-king分析例：输入：220 30.60.650.70.750.80.850.950.70.750.80.80.90.95输出：0.6375设F[I,money]表示将money的资金用到前I项备用件中去的最大可靠性，则有

F[I,money]=max{F[I-1,money–k*Cost[I]]}(0<=I<=n,0<=K<=moneydivCost(I))初始：F[0,0]=0目标：F[n,C]=0动态规划-king快餐问题

Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0<=0<=10)，第四行为N个不超过10000的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出:每天套餐的最大产量。

动态规划-king分析本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状态表示：用p[i,j,k]表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。用r[i,j,k]表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。态转移方程：p[i,j,k]=Max{p[i-1,j1,k1]+r[i,j-j1,k-k1]}(0<=j1<=j<=100,0<=k1<=k<=100,

且(j-j1)*p1+(k-k1)*p2<=T[i]---第i条生产线的生产时间)r[i,j-j1,k-k1]=(T[i]-(j-j1)*p1+(k-k1)*p2)divp3;此算法的时间复杂度为O(N*1004),动态规划-king优化在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min｛100divA，100divB，100divc｝），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：S1：读入数据。S2：贪心求上限并计算出一可行解，判断是否需进行下一步。S3：动态规划求解。S4：输出。动态规划-king其他优化方法1.存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。2.减少循环次数：在计算每一阶段状态过程中无疑要用到4重循环，我们可以这样修改每一重循环的起始值和终数，其中q1,q2为A，B上限值。原起始值改进后的起始值fori:=1tondofori:=1tondoforj:=0totot[i]divp1doforj:=0tomin(q1,tot[i]divp1)dofork:=0to(tot[i]-p1*j)divp2dofork:=0tomin(q2,(tot[i]-p1*j)divp2)doforj1:=0tojdoforj1:=max(0,j-t[i]divp1)tomin(j,tot[i-1]divp1)dofork1:=0tokdofork1:=max(0,k-(t[i]-(j-j1)*p1)divp2)tomin(k,(tot[i-1]-p1*j1)divp2)do动态规划-king石子合并在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据: 第一行为石子堆数N;

第二行为每堆石子数,每两个数之间用一空格分隔.输出数据: 从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.动态规划-king示例动态规划-king贪心法N=5石子数分别为346542。用贪心法的合并过程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24总分：61显然，贪心法是错误的。动态规划-king动态规划用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2<=k<=j)max[i,1]=0同样的，我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0<=k<=j)min[i,0]=0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。动态规划-king积木游戏一种积木游戏，游戏者有N块编号依次为1，2，…，N的长方体积木。第I块积木通过同一顶点三条边的长度分别为ai,bi,ci（i=1,2,…,N），1从N块积木中选出若干块，并将他们摞成M（1<=M<=N）根柱子，编号依次为1,2,…,M，要求第k根柱子的任意一块积木的编号都必须大于第K-1根柱子任意一块积木的编号（2<=K<=M）。2对于每一根柱子，一定要满足下面三个条件：除最顶上的一块积木外，任意一块积木的上表面同且仅同另一块积木的下表面接触；对于任意两块上下表面相接触的积木，若m,n是下面一块积木接触面的两条边（m>=n），x,y是上面一块积木接触面的两条边（x>=y），则一定满足m.>=x和n>=y；下面的积木的编号要小于上面的积木的编号。请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子的高度之和最大。动态规划-king积木游戏输入数据：文件的第一行是两个正整数N和M（1<=M<=N<=100）,分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来的N行是编号从1到N个积木的尺寸，每行有三个1至500之间的整数，分别表示该积木三条边的长度。同一行相邻两个数之间用一个空格符隔开。输出数据：文件只有一行，是一个整数，表示所求得的游戏方案中M根柱子的高度之和动态规划-king分析设（1）f[i,j,k]表示以第i块积木的第k面为第j根柱子的顶面的最优方案的高度总和；（2）block[i,k]记录每个积木的三条边信息（block[i,4]:=block[i,1];block[i,5]:=block[i,2]）。其中block[i,j+2]表示当把第i块积木的第j面朝上时所对应的高，即所增加的高度；（3）can[i,k,p,kc]表示第I块积木以其第k面朝上，第p块积木以第kc面朝上时，能否将积木I放在积木p的上面。1表示能，0表示不能。对于f[i,j,k],有两种可能：1.除去第I块积木，第j根柱子的最上面的积木为编号为p的，若第p块积木以第kc面朝上，必须保证当第I块积木以k面朝上时能够被放在上面，即can[i,k,p,kc]=1；2.第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为第p块积木，则此时第p块积木可以以任意一面朝上。则有：动态规划-king动态规划边界条件：f[1,1,1]:=block[1,1,3];f[1,1,2]:=block[1,1,4];f[1,1,3]:=block[1,1,5];f[i,0,k]:=0;(1<=i<=n,1<=k<=3);时间复杂度为O(n^2*m)动态规划-king免费馅饼SERKOI最新推出了一种叫做“免费馅饼”的游戏。游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央，手里拿着一个托盘。游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。动态规划-king免费馅饼输入数据：输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度W（1~99之间的奇数）和高度H（1~100之间的整数）。接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0~1000秒），水平位置、下落速度（1~100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。输出数据：输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。动态规划-king分析我们将问题中的馅饼信息用一个表格存储。表格的第I行第J列表示的是游戏者在第I秒到达第J列所能取得的分值。那么问题便变成了一个类似数字三角形的问题：从表格的第一行开始往下走，每次只能向左或右移动一格或两格，或不移动走到下一行。怎样走才能得到最大的分值。因此，我们很容易想到用动态规划求解。F[I,J]表示游戏进行到第I秒，这时游戏者站在第J列时所能得到的最大分值。那么动态转移方程为：

F[I,J]=Max{F[I-1,K]}+馅饼的分值(J-2<=K<=J+2)动态规划-king钉子和小球有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下面一排钉子的间隙。让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。我们知道小球落在第i个格子中的概率pi=，其中i为格子的编号，从左至右依次为0,1,...,n。现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。动态规划-king钉子和小球输入：第1行为整数n（2<=n<=50）和m（0<=m<=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中‘*’表示钉子还在，‘.’表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。输出：仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概率pm动态规划-king分析设三角形有n行，第i行（1<=i<=n）有i个铁钉位置，其编号为0..i-1；第n+1行有n+1个铁钉位置，排成n+1个格子，编号为0..n。设经