2022年动态规划经典教程 .pdf

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

1、动态规划经典教程引言：本人在做过一些题目后对DP 有些感想，就写了这个总结：第一节 动态规划基本概念一，动态规划三要素：阶段，状态，决策。他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的） 。下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就

2、去销售，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态 =_=|） 。每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。经过这个例子相信大家对动态规划有所了解了吧。下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE 网（

3、为什么无环呢？往下看）。对这个图进行拓扑排序，删除一个边后同时出现入度为0 的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i 求解时用到状态j 而状态 j 就解有用到状态k.状态 N。而求状态N 时有用到了状态i 这样求解状态的过程形成了环就没法用动态规划解答了，这也是上面用图论理解动态规

4、划中形成的图无环的原因。也就是说当前状态是前面状态的完美总结，现在与过去无关。 。当然，有是换一个划分状态或阶段的方法就满足无后效性了，这样的问题仍然可以用动态规划解。三，动态规划解决问题的一般思路。拿到多阶段决策最优化问题后，第一步要判断这个问题是否可以用动态规划解决，如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后，就要用下面介绍的方法解决问题了：（1）模型匹配法：最先考虑的就是这个方法了。挖掘问题的本质，如果发现问题是自己熟悉的某个基本的模型，就直接套用，但要小心其中的一些小的变动，现在考题办都是基本模型的变形套用时要小心条件，三思而后行。这些基本模型在先面的分类中将一一介绍。（

5、2）三要素法仔细分析问题尝试着确定动态规划的三要素，不同问题的却定方向不同：先确定阶段的问题：数塔问题，和走路问题（详见解题报告）先确定状态的问题：大多数都是先确定状态的。先确定决策的问题：背包问题。（详见解题报告）一般都是先从比较明显的地方入手，至于怎么知道哪个明显就是经验问题了，多做题就会发现。（3）寻找规律法：这个方法很简单，耐心推几组数据后，看他们的规律，总结规律间的共性，有点贪心的意思。（4）边界条件法找到问题的边界条件，然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。（5）放宽约束和增加约束这个思想是在陈启锋的论文里看到的，具体内容就是给问题增加一些条件或删除一些条件使

6、问题变的清晰。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 46 页 - - - - - - - - - 第二节 动态规划分类讨论这里用状态维数对动态规划进行了分类：1.状态是一维的11 下降/非降子序列问题：问题描述：挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解 在一个无序的序列a1,a2,a3,a4an 里，找到一个最长的序列满足：ai=aj=ak=am,且 ijk ajak am,且 ijk m.（最长下降子序列） 。问题分析：如果前 i-1 个数中用到

7、ak (akai 或 akai(或aj=ai)，optj+1 就是 opti 的值； 用方程表示为： 我习惯了这种写法，但不是状态转移方程的标准写法 opti=max(optj)+1 (0=ji 且 aj=ai) 最长非降子序列 opti=max(optj)+1 (0=jai) 最长下降子序列 实现求解的部分代码：opt0:=maxsize ；maxsize 为 maxlongint 或 -maxlongint for i:=1 to n do for j:=0 to i-1 do if ( ajai) and (optj+1opti) then opti:=optj+1; ans:=-max

8、longint; for i:=1 to n do if optians then ans:=opti; ans 为最终解 复杂度：从上面的实现不难看出时间复杂度为O（N2） ，空间复杂度O（N） ；例题 1 拦截导弹(missile.pas/c/cpp) 来源： NOIP1999( 提高组 ) 第一题【问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来

9、的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【输入文件】 missile.in 单独一行列出导弹依次飞来的高度。【输出文件】 missile.out 两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数【输入样例】389 207 155 300 299 170 158 65 【输出样例】6 2 【问题分析】有经验的选手不难看出这是一个求最长非升子序列问题，显然标准算法是动态规划。以导弹依次飞来的顺序为阶段，设计状态opti 表示前 i 个导弹中拦截了导弹i 可以拦截最多能拦截到的导弹的

10、个数。状态转移方程：opti=max(optj)+1 (hi=hj,0=j=ai) and (optj+1opti) then opti:=optj+1; anslen:=0; for i:=1 to n do if optianslen then anslen:=opti; fillchar(opt,sizeof(opt),0); a0:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if (ajopti) then opti:=optj+1; anstime:=0; for i:=1 to n do if optianstime

11、then anstime:=opti; end; procedure print; begin writeln(anslen); writeln(anstime); close(input); close(output); end; begin init; main; print; end. 例题二合唱队形(chorus.pas/c/cpp) 来源： NOIP2004( 提高组 ) 第一题N 位同学站成一排，音乐老师要请其中的(N-K) 位同学出列，使得剩下的K 位同学排成合唱队形。合唱队形是指这样的一种队形：设K 位同学从左到右依次编号为1，2， K，他们的身高分别为T1，T2， TK ，则

12、他们的身高满足T1.Ti+1 TK(1=i=K) 。你的任务是， 已知所有N 位同学的身高， 计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件chorus.in 的第一行是一个整数N(2=N=100) ，表示同学的总数。第一行有n 个整数，用空格分隔，第i 个整数 Ti(130=Ti=230) 是第 i 位同学的身高 (厘米 )。【输出文件】输出文件chorus.out 包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8 186 186 150 200 160 130 197 220 【样例输出】4 【数据规模】对于 50的数据，保证有n=2

13、0；对于全部的数据，保证有n=100。【问题分析】出列人数最少，也就是说留的人最多，也就是序列最长。这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于，包括他在内向左求最长上升子序列，向右求最长下降子序列。我们看一下复杂度：计算最长下降子序列的复杂度是O（N2） ，一共求N 次，总复杂度是O（N3） 。这样的复杂度对于这个题的数据范围来说是可以AC 的。但有没有更好的方法呢？其实最长子序列只要一次就可以了。因为最长下降（上升）子序列不受中间人的影响。只 要 用OPT1求 一 次 最 长 上 升 子 序 列 ， OPT2 求 一 次 最 长 下 降 子

14、序 列 。 这 样 答 案 就 是N-max(opt1i+opt2i-1). 复杂度由O（N3）降到了O（N2） 。【源代码】program chorus; const fin=chorus.in; fout=chorus.out; maxn=200; var opt1,opt2,a:array0.maxn of longint; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 46 页 - - - - - - - - - n,ans:longint; procedure

15、 init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); readln(n); for i:=1 to n do read(ai); end; procedure main; var i,j:longint; begin a0:=-maxlongint; for i:=1 to n do for j:=i-1 downto 0 do if (ajopt1i) then opt1i:=opt1j+1; an+1:=-maxlongint; for i:=n

16、downto 1 do for j:=i+1 to n+1 do if (ajopt2i) then opt2i:=opt2j+1; ans:=0; for i:=1 to n do if opt1i+opt2ians then ans:=opt1i+opt2i; end; procedure print; begin writeln(n-ans+1); close(input); close(output); end; begin init; main; print; end. 例题 3 Buy Low Buy Lower (buylow.pas/c/cpp) 来源 : USACO 4-3-

17、1 【问题描述】?逢低吸纳 ?是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀: 逢低吸纳 ,越低越买 这句话的意思是： 每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。给定连续的N 天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。以下面这个表为例, 某几天的股价是:天数1 2 3 4 5 6 7 8 9 10 11 12 股价68 69 54 64 68 64 70 67 78 62 98 87 这个例子中 , 聪明的投资者

18、(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买 4 次股票。一种买法如下(可能有其他的买法): 天数2 5 6 10 股价69 68 64 62 【输入文件】 buylow.in 第 1 行 : N (1 = N =aj,0=ji) ai 存第 i 天股价 最大的 opti 就是最终的解。第二问呢，稍麻烦一点。从问题的边界出发考虑问题，当第一问求得一个最优解opti=X 时，在 1 到 N 中如果还有另外一个optj=x 那么选取 J 的这个方案肯定是成立的。是不是统计所有的optj=x 的个数就是解了呢？显然没那么简单，因为选取这天的股票构成的方案不见得，看下面一个

19、例子：6 43 2 方案一：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 46 页 - - - - - - - - - 方案二：方案三：方案四：x=4 也就是所虽然opt5=X 和 opt6=X 但个数只有两个，而实际上应该有四个方案，但在仔细观察发现，构成 opt5=x 的这个方案中optj=x-1 的方案数有两个,optj=x-2的有一个， optj=x-3 的有一个显然这是满足低归定义的设计函数F（i）表示前 I 张中用到第i 张股票的方案数。递推式：1 (i=0

20、) F(i)= Sum(F(j) (0=jai,optj=opti-1) sum 代表求和 答案 =sum(F(j) 0jai) and (optj+1opti) then opti:=optj+1; for i:=1 to n do begin j:=i-1; while (j0) and (optioptj) or (aiaj) do dec(j); nexti:=j; end; F0,1:=1; for i:=1 to n+1 do for j:=i-1 downto nexti do if (optj=opti-1) and (ajai) then Hinc(Fi,Fj); end;

21、procedure print; var i,top,m:longint; begin write(optn+1-1, ); top:=maxsize; while (top1) and (Fn+1top=0) do dec(top); write(Fn+1,top); for i:=top-1 downto 1 do begin m:=Fn+1,i; while mmaxsize div 10 do begin write(0); m:=m*10; end; write(Fn+1,i); end; writeln; close(input); close(output); end; begi

22、n init; main; print; end. 例题 4 船(ships.pas/c/cpp) 来源： 奥赛经典 （提高篇）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 46 页 - - - - - - - - - 【问题描述】PALMIA 国家被一条河流分成南北两岸，南北两岸上各有N 个村庄。 北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线

23、相交（如果相交，则很可能导致碰船）。你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。【输入文件】 ships.in 输入文件由几组数据组成。每组数据的第一行有2 个整数 X， Y， 中间有一个空格隔开， X 代表 PALMIA河的长度（ 10=X=6000 ） ，Y 代表河的宽度（10=Y=100 ） 。第二行包含整数N，表示分别坐落在南北两岸上的村庄的数目（1=N=5000 ） 。在接下来的N 行中，每一行有两个非负整数C，D，由一个空格隔开，分别表示这一对朋友村庄沿河岸与PALMIA 河最西边界的距离（C 代表北岸的村庄，D 代表南岸的村庄） ，不存在同

24、岸又同位臵的村庄。最后一组数据的下面仅有一行，是两个0，也被一空格隔开。【输出文件】 ships.out 对输入文件的每一组数据，输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。【输入样例】30 4 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2 0 0 【输出样例】4 【问题分析】这道题目相对来说思考难度较高，从字面意义上看不出问题的本质来，有点无法下手的感觉。这里我给大家推荐两种思考这类问题的方法。法一：寻找规律法（我前面总结提到的第3 个方法）寻找规律自然要推几组数据，首先当然有从样例入手；仔细观察上图：红色航线是合法的，那么他们满足什么规律呢？C1

25、 C2 C3 C4 北岸红线的端点：4 9 15 17 南岸红线的端点：2 8 12 17 D1 D2 D3 D4 不难看出无论线的斜率如何，都有这样的规律：C1C2C3C4 且D1D2D3D4 如果我们把输入数据排升序，问题变抽象为：在一个序列（ D）里找到最长的序列满足DIDJDk 且 ijk 这样的话便是典型的最长非降子序列问题了。 。 。法二：边界条件法（我前面总结提到的第4 个方法）边界法其实就是把数据往小了缩，显然N=1 是答案是1。N=2 时呢？考虑这样一组数据：N=2 C1 D1 C2 D2 当 C1D2 那么一定会相交，反之则不会相交。当 C1 C2 时，如果 D1D2 那么

26、一定会相交，反之则不会相交。N=3 C1 D1 C2 D2 C3 D3 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 46 页 - - - - - - - - - 其实不用在推导N=3 了，有兴趣的可以推导去。看N=2 时就能得出：对于任意两条航线如果满足CiCj 且 DiDj 则两条航线不相交。这样的话要想在一个序列里让所有的航线都不相交那比然满足，C1C2C3Cans且 D1D2D3 Dans ，也就是将C 排序后求出最长的满足这个条件的序列的长度就是解。这样分析后

27、显然是一个最长非降子序列问题。复杂度：排序可以用O（ nlogn）的算法，求最长非降子序列时间复杂度是O(n2). 总复杂度为O（n2）. 【源代码】program ships; const fin=ships.in; fout=ships.out; maxn=5010; type retype=record C,D:longint; end; var x,y,n,ans:longint; a:array0.maxn of retype; opt:array0.maxn of longint; procedure init; var i:longint; begin readln(n); fo

28、r i:=1 to n do read(ai.c,ai.d); end; procedure quick(L,r:longint); var i,j,x:longint; y:retype; begin i:=L; j:=r; x:=a(i+j) div 2.c; repeat while ai.cx do dec(j); if ij; if jL then quick(L,j); if ir then quick(i,r); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),0); quick(1,n);

29、 for i:=1 to n do for j:=0 to i-1 do if (aj.dopti) then opti:=optj+1; ans:=-maxlongint; for i:=1 to n do if ansopti then ans:=opti; writeln(ans); end; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(x,y); while (x+y0) do begin init; main; read(x,y); end; close(input

30、); close(output); end. 1.2 背包问题首先说说背包问题的基本模型：现有 N 个物品，每个物品的价值为V，重量为W。求用一个载重量为S 的背包装这写物品，使得所装物品的总价值最高。背包问题用贪心和搜索解，当然效果不佳，不过在我的贪心和搜索总结中会说到。显然标准的解法是动态规化，我在解决这个问题时习惯设计一维状态，还可以设计二维的，二维状态在下面会讲，现在只讨论用一维状态实现背包问题。背包问题的分类：(1)小数背包 :物品的重量是实数，如油，水等可以取1.67 升(2)整数背包： 0/1 背包：每个物品只能选一次，或不选。不能只选一部分部分背包：所选物品可以是一部分。(3)

31、多重背包：背包不只一个。小数背包：在贪心总结中会细讲。整数背包：部分背包：同小数背包。0/1 背包：这个问题是最经常出现的问题，应该熟练掌握。我们先看一下0/1 背包的简化版：现有 N 个物品，每个物品重量为W，这些物品能否使在载重量为S 的背包装满 （即重量和正好为S） ？如过不能那能使物品重量和最重达到多少？针对这一问题我们以物品的个数分阶段，设计一个状态opti 表示载重量为i 的背包可否装满，显然opti 的基类型是boolean。决策是什么呢？当要装第i 个物品时，如果前i-1 个物品可以使载重为k 的背包装满，那么载重为k+wi 的背包就可名师资料总结 - - -精品资料欢迎下载

32、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 46 页 - - - - - - - - - 以装满。于是对于一个optj 来说，只要optj-wi 是 true（表示可装满）那optj 就可以装满，但要注意：针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几次，因为k+wi 可装满那k+wi+wi就可装满，但实际上是装不满的因为物品只有一个。解决这个问题很简单，只要逆向推导就OK 了。这样划分阶段，设计状态，满足无后效性和么？显然对与一个每一个阶段都是独立的，物品的顺序并不影响求解，因为装物

33、品的次序不限。而对于 optj只考虑 optj-wi 而不考虑后面的，所以满足无后效性。有了上面的分析不难写出状态转移方程：optj:=optj-w1 optj-wi=true 时间复杂度：阶段数 O(S)* 状态数（ O(N) ）*转移代价（ O(1) ）=O（SN）下面看几个例题：例题 5 装箱问题(pack.pas/c/cpp) 来源： NOIP2001(普及组 ) 第四题【问题描述】有一个箱子容量为V（正整数， 0 V 20000） ，同时有 n 个物品（ 0n30，每个物品有一个体积（正整数） 。要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。【输入文件】第一行一个正

34、整数V 表示箱子的容量，第二行一个正整数N 表示物品个数，接下来N 行列出这N个物品各自的体积。【输出文件】单独一行，表示箱子最小的剩余空间。【输入样例】24 6 8 3 12 7 9 7 【输出样例】0 【问题分析】本题是经典的0/1 背包问题，并且是0/1 背包的简化版，把箱子看做背包，容量看做载重量，体积看做重量，剩余空间最小也就是尽量装满背包。于是这个问题便成了：有一个栽重量为V 的背包，有N 个物品，尽量多装物品，使背包尽量的重。设计一个状态opti 表示重量 i 可否构成。状态转移方程：optj:=optj-w1 optj-wi=true 最终的解就是v-x （x=n 且 optx

35、=true 且 optx+1.n=false ） 。【源代码1】program pack; const fin=pack.in; fout=pack.out; maxv=20010; maxn=100; var opt:array0.maxv of boolean; w:array0.maxn of longint; v,n,x:longint; procedure init; var i:longint; begin assign(input,fin); reset(input); assign(output,fout); rewrite(output); read(v); read(n);

36、 for i:=1 to n do read(wi); end; procedure main; var i,j:longint; begin fillchar(opt,sizeof(opt),false); opt0:=true; for i:=1 to n do for j:=v downto wi do if optj-wi then optj :=true; x:=v; while not optx do dec(x); end; procedure print; begin writeln(v-x); close(input); close(output); end; begin i

37、nit; main; print; end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 46 页 - - - - - - - - - 例题 6 砝码称重来源： NOIP1996 （提高组）第四题【问题描述】设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重=1000） ，用他们能称出的重量的种类数。【输入文件】a1 a2 a3 a4 a5 a6 （表示 1g 砝码有 a1个， 2g 砝码有 a2 个， 20g 砝码有 a6 个，中间有空格） 。【输

38、出文件】Total=N （N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。【输入样例】1 1 0 0 0 0 【输出样例】TOTAL=3 【问题分析】把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6 个砝码的重量wi, wi 1,2,3,5,10,20 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。这样一改就是经典的0/1 背包问题的简化版了，求解方法完全和上面说的一样，这里就不多说了，只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。【源代码1】program P4; const maxn=1010; w:array1.6

39、of longint=(1,2,3,5,10,20); var opt:array0.maxn of boolean; a:array1.6 of longint; procedure init; var i:longint; begin for i:=1 to 6 do read(ai); end; procedure main; var i,j,k:longint; begin fillchar(opt,sizeof(opt),false); opt0:=true; for i:=1 to 6 do for j:=1 to ai do for k:=maxn downto wi do if

40、 optk-wi then optk:=true; end; procedure print; var ans,i:longint; begin ans:=0; for i:=1 to maxn do if opti then inc(ans); writeln(ans); end; begin init; main; print; end. 例题 7 积木城堡来源： vijos P1059 【问题描述】XC 的儿子小XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC 是一个比他爸爸XC 还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面

41、的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。任务：请你帮助小XC 编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效

42、果。【输入文件】第一行是一个整数N(N0 do begin inc(top); atop:=m; inc(tothig,m); read(m); end; for i:=1 to top do for j:=tothig downto 1 do if (j-ai=0) and (optii,j-ai) then optii,j:=true; end; ans:=maxhig; while not opt1,ans do dec(ans); while not can(ans) do dec(ans); writeln(ans); end; begin init; main; end. 回顾上面

43、的内容充分说明动态规划的本质就是递推。其实按照我的理解（动规涉及最优决策，递推是单纯的总结）背包问题的简化版更准确点算是递推而非动态规划，至于动归和递推之间的界线本来就很模糊（至少我这么认为）把它看做什么都可以，没必要咬文嚼字。回到 0/1 背包的原问题上（如果你忘了就去上面看看）。如果在不知道这个模型的情况下我们怎么做这个题呢？这就要用到第一节提到的方法二：三要素法。题目中明确说明对于一个物品要不就拿走要不就放下，其实题目赤裸裸的告诉我们决策就是不拿（用0 表示）或拿（用1 表示） 。这样想都不用想就知道了决策，这也是本题的突破口。知道了决策写个搜索的程序应该是很轻松的了。那么阶段是什么呢？

44、显然，给你一堆东西让你往包里塞，你当然是一个一个的那来，塞进去。那么阶段很明显就是物品的个数。状态又是什么呢？有的人在装东西是有个习惯（比如说我）就是先把东西分类，然后把同类的东西打个小包，最后在把小包放进去，我们可以按这个思想给物品打一些小包，也就是按照单位为1 的递增的顺序准备好多小包，比如载重是6 的包，可以为它准备载重是1，2，3，4，5 的小包。这样状态就可以想出来了：设计状态opti ，j表示装第i 个物品时载重为j 的包可以装到的最大价值。opti-1,j (j-wi0) 状态转移方程：opti,j= maxopti-1,j,opti-1,j-wi+vi (j-wi=0,i0)

45、(wi: 第 i 个物品的重量，vi 第 i 个物品的价值 ) 解释：要载重为j 的背包空出wi （j-wi ）的空间且装上第i 个物品，比不装获得的价值大就装上它。边界条件： opt0,i=0; (i 1.S) 注：这种二维的状态表示应该在下节讲，但是为了方便理解先在这里说了。上面的方法动态规划三要素都很明显，实现也很简单。但是在我初学背包时却用另外一种一维的状态表示法。用第一节说的思考方法五（放宽约束和增加约束）在重新思考一下这个问题：怎么放宽约束呢？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -

46、- - - - 第 10 页，共 46 页 - - - - - - - - - 把题目中的价值去掉，不考虑价值即最优就变成背包问题的简化版了。那简化版的求解对我们有何启示呢？再一次增加约束：背包只能装满。显然对于N 个装满背包的方案中只要找到一个价值最大的就是问题的解。那么装不满怎么办呢？其实装不满背包，它总要达到一定的重量（X） 。我们可以把这种情况看作是装满一个载重为X 的小包。总结一下上面的思维过程：放宽约束让我们找到问题的突破口和背包问题简化版一样，我们可以却定载重为S 的背包是否可以装满。增加约束让我们找到问题的求解方法在装满背包的方案中选择最优的一个方案。这样问题就解决了。设计一个

47、状态optj 表示装满载重为j 的背包可获得的最大价值。对于第i 个物品，只要optj-wi可以装满且optj-wi+vi比 optj 大就装上这个物品（更新optj ） 。怎么使 optj 既有是否构成又有最优的概念呢？optj 只表示最优，只不过使初始条件+1，判断 optj 是否为 0，如果 optj=0 说明 j 装不满。边界条件： opt0=1; 状态转移方程：optj=maxoptj-wi (0in,wi=j=S) 问题解：ans=maxopti-1 (0i=s) 时间复杂度：阶段数O(S)* 状态数（ O(N)） *转移代价（ O(1)）=O（SN）下面看几个例题：例题 8 采药

48、(medic.pas/c/cpp) 来源： NOIP2005 （普及组）第三题【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。 医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：?孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。?如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件medic.in 的第一行有两个整数T（ 1 = T = 1000 ）和 M（

49、1 = M = 100 ） ，用一个空格隔开，T 代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的M 行每行包括两个在1 到 100之间（包括1 和 100）的整数，分别表示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件medic.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【输入样例】70 3 71 100 69 1 1 2 【输出样例】3 【数据规模】对于 30%的数据， M = 10 ；对于全部的数据，M y then max:=x else max:=y; end; procedure main; var i,j:l

50、ongint; begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 46 页 - - - - - - - - - fillchar(opt,sizeof(opt),0); for i:=1 to n do for j:=1 to t do if j-wi0) and (optj-wi+vioptj) then optj:=optj-wi+vi; ans:=-maxlongint; for i:=1 to t do if optians then ans:=opt