2022年动态规划详细教程 .pdf

《2022年动态规划详细教程 .pdf》由会员分享，可在线阅读，更多相关《2022年动态规划详细教程 .pdf（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、动态规划的有关讲解（详细！）状态是一维的。我用这题的思想来为大家入个门。下降 /非降子序列问题：问题描述： 挖掘题目的本质，一但抽象成这样的描述就可以用这个方法解在一个无序的序列a1,a2,a3,a4 ,an里， 找到一个最长的序列满足：ai=aj=ak,=am,且 ijk ,ajak,am,且 ijk ,m.（最长下降子序列）。PS：如果前 i-1 个数中用到ak (akai 或 akai(或 aj=ai)，optj+1 就是 opti 的值；用方程表示为：opti=max(optj)+1(0=ji 且 aj=ai) 最长非降子序列 opti=max(optj)+1(0=jai) 最长下降子

2、序列 实现求解的部分代码：opt0:=maxsize ；maxsize 为 maxlongint 或-maxlongintfor i:=1 to n do （这里是从头到尾，当然也可以从尾到头，可以这样表示for i:=n downto1 do ）for j:=0 to i-1 do( 上面如果是从尾到头，那么这里可以for j:=i+1 to n do)if ( ajai) and (optj+1opti) then opti:=optj+1;ans:=-maxlongint;for i:=1 to n do if optians then ans:=opti; ans 为最终解 复杂度：从

3、上面的实现不难看出时间复杂度为O（N2），空间复杂度O（N）；拦截导弹(missile.pas/c/cpp)来源： NOIP1999( 提高组 ) 第一题【问题描述】某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000 的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。【输入文

4、件】 missile.in单独一行列出导弹依次飞来的高度。【输出文件】 missile.out两行，分别是最多能拦截的导弹数，要拦截所有导弹最少要配备的系统数【输入样例】389 207 155 300 299 170 158 65【输出样例】62PS：这道题的第一问我们不难想到就是求最长下降子序列。所以这题我们可以使用动态规划来实现。以导弹依次飞来的顺序为阶段，设计状态opti 表示前 i 个导弹中拦截了导弹i 可以拦截最多能拦截到的导弹的个数。状态转移方程：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - -

5、- - - - - 第 1 页，共 36 页 - - - - - - - - - opti=max(optj)+1 (hi=hj,0=j=ai) and (optj+1opti) thenopti:=optj+1;anslen:=0;for i:=1 to n doif optianslen thenanslen:=opti;fillchar(opt,sizeof(opt),0);a0:=-maxlongint;for i:=1 to n dofor j:=i-1 downto 0 do名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - -

6、 - 名师精心整理 - - - - - - - 第 2 页，共 36 页 - - - - - - - - - if (ajopti) thenopti:=optj+1;anstime:=0;for i:=1 to n doif optianstime thenanstime:=opti;end;procedure print;beginwriteln(anslen);writeln(anstime);close(input);close(output);end;begininit;main;print;end. 合唱队形(chorus.pas/c/cpp)来源： NOIP2004( 提高组 )

7、 第一题N 位同学站成一排，音乐老师要请其中的(N-K) 位同学出列，使得剩下的K 位同学排成合唱队形。合唱队形是指这样的一种队形：设K 位同学从左到右依次编号为1，2, ， K，他们的身高分别为T1，T2，, ， TK， 则他们的身高满足 T1.Ti+1 ,TK(1=i=K) 。你的任务是，已知所有N 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。【输入文件】输入文件 chorus.in 的第一行是一个整数N(2=N=100) ，表示同学的总数。第一行有n 个整数，用空格分隔，第i 个整数Ti(130=Ti=230) 是第 i 位同学的身高 (厘米 )。【输出文件】

8、输出文件 chorus.out 包括一行，这一行只包含一个整数，就是最少需要几位同学出列。【样例输入】8186 186 150 200 160 130 197 220【样例输出】4【数据规模】对于 50的数据，保证有n=20；对于全部的数据，保证有n=100。PS：所谓的合唱队队形就是中间最高然后依次从两边递减。题目要求出队人数最少，于是我们可以抽象的想象成从左到最高的人是最长上升子序列，从最高人的人到右边是最长下降子序列。我们来看一下复杂度：如果采用枚举中间人的话，计算最长上升或下降子序列复杂度O（n2）一共求 N 次，所以复杂度变为O（n3）。这个复杂度对这题的数据已经可以解决，但不是最优

9、的方法。其实最长上升或下降子序列只要一次就可以了，因为最长最长上升或下降子序列不受中间人的影响。只要用OPT1 求一次最长上升子序列， OPT2 求一次最长下降子序列。这样答案就是N-max(opt1i+opt2i-1).（i 是从 1 到 n）。这样我们就把复杂度从O（n3）降到了O（n2）。参考程序：program chorus;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 36 页 - - - - - - - - - constmaxn=200;varopt1,o

10、pt2,a:array0.maxn of longint;n,ans:longint;procedure init;vari:longint;beginassign(input, chorus.out);reset(input);assign(output, chorus.in);rewrite(output);readln(n);for i:=1 to n doread(ai);end;procedure main;vari,j:longint;begina0:=-maxlongint;for i:=1 to n dofor j:=i-1 downto 0 doif (ajopt1i) th

11、enopt1i:=opt1j+1;an+1:=-maxlongint;for i:=n downto 1 dofor j:=i+1 to n+1 doif (ajopt2i) thenopt2i:=opt2j+1;ans:=0;for i:=1 to n doif opt1i+opt2ians thenans:=opt1i+opt2i;end;procedure print;beginwriteln(n-ans+1);close(input);close(output);end;begininit;main;print;end.船名师资料总结 - - -精品资料欢迎下载 - - - - - -

12、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 36 页 - - - - - - - - - (ships.pas/c/cpp)来源：奥赛经典（提高篇）【问题描述】PALMIA国家被一条河流分成南北两岸，南北两岸上各有N 个村庄。北岸的每一个村庄有一个唯一的朋友在南岸，且他们的朋友村庄彼此不同。每一对朋友村庄想要一条船来连接他们，他们向政府提出申请以获得批准。由于河面上常常有雾，政府决定禁止船只航线相交（如果相交，则很可能导致碰船）。你的任务是编写一个程序，帮助政府官员决定批准哪些船只航线，使得不相交的航线数目最大。【输入文件】 sh

13、ips.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对输入文件的每一组数据，输出文件应在连续的行

14、中表示出最大可能满足上述条件的航线的数目。【输入样例】30 4722 42 610 315 129 817 174 20 0【输出样例】4PS：这道题目相对来说思考难度较高，从字面意义上看不出问题的本质来，有点无法下手的感觉。这里我给大家推荐两种思考这类问题的方法。法一：寻找规律法（我前面总结提到的第3 个方法）寻找规律自然要推几组数据，首先当然有从样例入手；仔细观察上图：红色航线是合法的，那么他们满足什么规律呢？C1 C2 C3 C4北岸红线的端点 ： 4 9 15 17南岸红线的端点 ： 2 8 12 17D1 D2 D3 D4不难看出无论线的斜率如何，都有这样的规律：C1C2C3C4 且

15、 D1D2D3D4如果我们把输入数据排升序，问题变抽象为：在一个序列（ D）里找到最长的序列满足DIDJDk , 且ijk这样的话便是典型的最长非降子序列问题了。法二：边界条件法（我前面总结提到的第4 个方法）边界法其实就是把数据往小了缩，显然N=1 是答案是 1。N=2 时呢？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 36 页 - - - - - - - - - 考虑这样一组数据：N=2C1 D1C2 D2当 C1D2 那么一定会相交，反之则不会相交。当 C1 C

16、2 时，如果 D1D2 那么一定会相交，反之则不会相交。N=3C1 D1C2 D2C3 D3,其实不用在推导N=3 了，有兴趣的可以推导去。看N=2 时就能得出：对于任意两条航线如果满足CiCj 且 DiDj 则两条航线不相交。这样的话要想在一个序列里让所有的航线都不相交那比然满足，C1C2C3,Cans且 D1D2D3 , Dans ，也就是将 C 排序后求出最长的满足这个条件的序列的长度就是解。这样分析后显然是一个最长非降子序列问题。复杂度：排序可以用O（nlogn）的算法，求最长非降子序列时间复杂度是O(n2).总复杂度为O（n2）。参考程序 :program ships;constma

17、xn=5010;typeretype=recordC,D:longint;end;varx,y,n,ans:longint;a:array0.maxn of retype;opt:array0.maxn of longint;procedure init;vari:longint;beginreadln(n);for i:=1 to n doread(ai.c,ai.d);end;procedure quick(L,r:longint);vari,j,x:longint;y:retype;begini:=L;j:=r;x:=a(i+j) div 2.c;repeatwhile ai.cx do

18、dec(j);if ij;if jL then quick(L,j);if ir then quick(i,r);end;procedure main;vari,j:longint;beginfillchar(opt,sizeof(opt),0);quick(1,n);for i:=1 to n dofor j:=0 to i-1 doif (aj.dopti) thenopti:=optj+1;ans:=-maxlongint;for i:=1 to n doif ansopti thenans:=opti;writeln(ans);end;beginassign(input,ships.i

19、n);reset(input);assign(output,ships.out);rewrite(output);read(x,y);while (x+y0) dobegininit;main;read(x,y);end;close(input);close(output);end.背包问题我参考了背包九讲等资料作出了如下整理。首先说说背包问题的基本模型：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 36 页 - - - - - - - - - 现有 N 个物品，每个物

20、品的价值为V，重量为 W。求用一个载重量为S 的背包装这写物品，使得所装物品的总价值最高。背包问题用贪心和搜索解，当然效果不佳，不过在我的贪心和搜索总结中会说到。显然标准的解法是动态规化，我在解决这个问题时习惯设计一维状态，还可以设计二维的，二维状态在下面会讲，现在只讨论用一维状态实现背包问题。背包问题的分类：（1）小数背包 :物品的重量是实数，如油，水等可以取1.67 升,（2）整数背包 ：部分背包：所选物品可以是一部分。0/1 背包：每个物品只能选一次，或不选。不能只选一部分（3）多重背包 ：背包不只一个。部分背包：同小数背包。0/1 背包 ：这个问题是最经常出现的问题，应该熟练掌握。我们

21、先看一下0/1 背包的简化版：现有 N 个物品，每个物品重量为W，这些物品能否使在载重量为S 的背包装满（即重量和正好为S）？如过不能那能使物品重量和最重达到多少？针对这一问题我们以物品的个数分阶段，设计一个状态opti 表示载重量为i 的背包可否装满，显然opti 的基类型是boolean。决策是什么呢 ？当要装第 i 个物品时，如果前i-1 个物品可以使载重为k 的背包装满，那么载重为k+wi 的背包就可以装满。于是对于一个optj 来说，只要 optj-wi 是 true（表示可装满）那optj 就可以装满，但要注意：针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几

22、次，因为k+wi 可装满那 k+wi+wi就可装满， 但实际上是装不满的因为物品只有一个。解决这个问题很简单，只要逆向推导就 OK 了。这样划分阶段，设计状态，满足无后效性和么？显然对与一个每一个阶段都是独立的，物品的顺序并不影响求解，因为装物品的次序不限。而对于optj 只考虑 optj-wi 而不考虑后面的，所以满足无后效性。有了上面的分析不难写出状态转移方程：optj:=optj-w1 optj-wi=true时间复杂度：阶段数 O(S)*状态数（ O(N) ）*转移代价（ O(1)）=O（SN）像装箱，采药等问题都是背包问题转变过来的。在将转移方程化为实际代码时，一共可以有3 种写法，

23、到时我会一一列举，让大家开阔思路。装箱问题(pack.pas/c/cpp)来源： NOIP2001( 普及组 ) 第四题【问题描述】有一个箱子容量为V（正整数， 0 V 20000），同时有n 个物品（ 0n 30，每个物品有一个体积（正整数）。要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。【输入文件】第一行一个正整数V 表示箱子的容量，第二行一个正整数N 表示物品个数，接下来N 行列出这 N 个物品各自的体积。【输出文件】单独一行，表示箱子最小的剩余空间。【输入样例】2468312797【输出样例】0名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

24、- - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 36 页 - - - - - - - - - PS：本题是经典的0/1 背包问题，并且是0/1 背包的简化版，把箱子看做背包，容量看做载重量，体积看做重量，剩余空间最小也就是尽量装满背包。于是这个问题便成了：有一个栽重量为V 的背包，有N 个物品，尽量多装物品，使背包尽量的重。设计一个状态opti 表示重量i 可否构成。状态转移方程： optj:=optj-wi optj-wi=true最终的解就是v-x （x0)and(optj-wi+wi=optj) then optj :=optj-wi+w

25、i;（最后 V 背包能装的最大容量是optv-1, 因为一开始opt0:=1 ）。3、这是另一种整数数组来表示该方程代码。opt0:=0;for i:=1 to n dofor j:=v downto wi doif (optj-wi+wi=optj) then optj :=optj-wi+wi;（最后 V 背包能装的最大容量为optv ）。这里大家会觉得2 和 3 是一样的，其实如果大家跟踪的话就会发现，第2 种比第 3 种好，为什么呢？因为第2 种的替换率比第3 种少，也就是说一旦数据过大的话第2 种比第 3 种更优。参考程序：program pack;constmaxv=20010;m

26、axn=100;varopt:array0.maxv of boolean;w:array0.maxn of longint;v,n,x:longint;procedure init;vari:longint;beginassign(input, pack.in);reset(input);assign(output, pack.out);rewrite(output);read(v);read(n);for i:=1 to n doread(wi);end;procedure main;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

27、- - 名师精心整理 - - - - - - - 第 9 页，共 36 页 - - - - - - - - - vari,j:longint;beginfillchar(opt,sizeof(opt),false);opt0:=true;for i:=1 to n dofor j:=v downto wi doif optj-wi then optj :=true;x:=v;while not optx do dec(x);end;procedure print;beginwriteln(v-x);close(input);close(output);end;begininit;main;pr

28、int;end. 砝码称重来源： NOIP1996（提高组）第四题【问题描述】设有 1g、2g、3g、5g、10g、20g 的砝码各若干枚（其总重=1000），用他们能称出的重量的种类数。【输入文件】a1 a2 a3 a4 a5 a6（表示 1g 砝码有 a1个， 2g砝码有 a2个， , ， 20g 砝码有 a6个，中间有空格）。【输出文件】Total=N（N 表示用这些砝码能称出的不同重量的个数，但不包括一个砝码也不用的情况）。【输入样例】1 1 0 0 0 0 【输出样例】TOTAL=3PS：把问题稍做一个改动，已知 a1+a2+a3+a4+a5+a6个砝码的重量wi, wi 1,2,3

29、,5,10,20 其中砝码重量可以相等，求用这些砝码可称出的不同重量的个数。这样一改就是经典的0/1 背包问题 的简化版了，求解方法完全和上面说的一样，这里就不多说了，只是要注意这个题目不是求最大载重量，是统计所有的可称出的重量的个数。参考程序：program P4;constmaxn=1010;w:array1.6 of longint=(1,2,3,5,10,20);varopt:array0.maxn of boolean;a:array1.6 of longint;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心

30、整理 - - - - - - - 第 10 页，共 36 页 - - - - - - - - - procedure init;vari:longint;beginfor i:=1 to 6 doread(ai);end;procedure main;vari,j,k:longint;beginfillchar(opt,sizeof(opt),false);opt0:=true;for i:=1 to 6 dofor j:=1 to ai dofor k:=maxn downto wi doif optk-wi then optk:=true;end;procedure print;varan

31、s,i:longint;beginans:=0;for i:=1 to maxn doif opti theninc(ans);writeln(ans);end;begininit;main;print;end. 积木城堡来源： vijos P1059【问题描述】XC 的儿子小 XC 最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的，城堡的每一层是一块积木。小XC 是一个比他爸爸XC 还聪明的孩子，他发现垒城堡的时候，如果下面的积木比上面的积木大，那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。小 XC 想把自己垒的城堡送给幼儿园里漂亮的女孩子们，这样可以增加他的好

32、感度。为了公平起见，他决定把送给每个女孩子一样高的城堡，这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了，他灵机一动，想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木，使得最终每座城堡都一样高。为了使他的城堡更雄伟，他觉得应该使最后的城堡都尽可能的高。任务：请你帮助小XC 编一个程序，根据他垒的所有城堡的信息，决定应该移去哪些积木才能获得最佳的效果。【输入文件】第一行是一个整数N(N0 dobegininc(top);atop:=m;inc(tothig,m);read(m);end;

33、for i:=1 to top dofor j:=tothig downto 1 doif (j-ai=0) and (optii,j-ai) thenoptii,j:=true;end;ans:=maxhig;while not opt1,ans do dec(ans);while not can(ans) dodec(ans);writeln(ans);end;begininit;main;end.阶段总结回顾上面的内容充分说明动态规划的本质就是递推。其实按照我的理解（动规涉及最优决策，递推是单纯的总结）背包问题的简化版更准确点算是递推而非动态规划，至于动归和递推之间的界线本来就很模糊（至

34、少我这么认为）把它看做什么都可以，没必要咬文嚼字。回到 0/1 背包的原问题上（如果你忘了就去上面看看）。如果在不知道这个模型的情况下我们怎么做这个题呢？这就要用到第一节提到的方法二：三要素法 。题目中明确说明对于一个物品要不就拿走要不就放下，其实题目赤裸裸的告诉我们决策就是不拿 （用 0 表示）或拿（用1 表示）。这样想都不用想就知道了决策，这也是本题的突破口。知道了决策写个搜索的程序应该是很轻松的了。那么 阶段是什么呢 ？显然，给你一堆东西让你往包里塞，你当然是一个一个的那来，塞进去。那么阶段很明显就是物品的个数。状态又是什么呢 ？有的人在装东西是有个习惯（比如说我）就是先把东西分类，然后

35、把同类的东西打个小包，最后在把小包放进去，我们可以按这个思想给物品打一些小包，也就是按照单位为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) (wi: 第 i 个物品的重量， vi 第 i 个物品的价值 )解释：要载重为j 的背包空出wi （j-wi ）的空间且装上第i 个物品，比不装获得的价值大就装上它

36、。边界条件 ：opt0,i=0; (i 1.S)注：这种二维的状态表示应该在下节讲，但是为了方便理解先在这里说了。上面的方法动态规划三要素都很明显，实现也很简单。但是在我初学背包时却用另外一种一维的状态表示法。用第一节说的思考方法五（放宽约束和增加约束）在重新思考一下这个问题：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 36 页 - - - - - - - - - 怎么放宽约束呢 ？把题目中的价值去掉，不考虑价值即最优就变成背包问题的简化版了。那简化版的求解对我们有

37、何启示呢？再一次增加约束：背包只能装满。显然对于 N 个装满背包的方案中只要找到一个价值最大的就是问题的解。那么装不满怎么办呢？其实装不满背包，它总要达到一定的重量（ X）。我们可以把这种情况看作是装满一个载重为X 的小包。总结一下上面的思维过程：放宽约束让我们找到问题的突破口和背包问题简化版一样，我们可以却定载重为S 的背包是否可以装满。增加约束让我们找到问题的求解方法在装满背包的方案中选择最优的一个方案。这样问题就解决了。设计一个状态optj 表示装满载重为j 的背包可获得的最大价值。对于第i 个物品，只要optj-wi 可以装满且 optj-wi+vi比 optj 大就装上这个物品（更新

38、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）采药(medic.pas/c/cpp)来源： NOIP2005（普及组）第三题【问题描述】辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为

39、了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？【输入文件】输入文件 medic.in 的第一行有两个整数T（1 = T = 1000 ）和 M （1 = M = 100 ），用一个空格隔开，T 代表总共能够用来采药的时间， M 代表山洞里的草药的数目。接下来的M 行每行包括两个在1 到 100 之间（包括1 和 100）的整数，分别表

40、示采摘某株草药的时间和这株草药的价值。【输出文件】输出文件 medic.out 包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。【输入样例】70 371 10069 11 2【输出样例】3【数据规模】对于 30%的数据， M = 10 ；对于全部的数据，M y then max:=xelse max:=y;end;procedure main;vari,j:longint;beginfillchar(opt,sizeof(opt),0);for i:=1 to n dofor j:=1 to t doif j-wi0) and (optj-wi+vioptj)

41、thenoptj:=optj-wi+vi;ans:=-maxlongint;for i:=1 to t doif optians then ans:=opti;end;procedure print;beginwriteln(ans-1);close(output);end;begininit;main;print;end. 开心的金明来源： NOIP2006（普及组）第二题【问题描述】金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一早金明就开始做预

42、算，但是他想买的东西太多了，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数15 表示，第 5 等最重要。他还从名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 36 页 - - - - - - - - - 因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j 件物品的价格为vj ，重要度为wj ，共选中了k 件物品，编号依次为j1.jk ，则所求的总

43、和为：vj1*wj1+.+vjk*wjk请你帮助金明设计一个满足要求的购物单.【输入文件】输入的第 1 行，为两个正整数，用一个空格隔开：N m （其中 N（30000）表示总钱数，m(25)为希望购买物品的个数。）从第 2 行到第 m+1 行，第 j 行给出了编号为j-1 的物品的基本数据，每行有2 个非负整数v p （其中 v 表示该物品的价格（v10000）， p 表示该物品的重要度（15）【输出文件】输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ =0) and (optj-vi0) and (optj-vi+vi*pioptj)thenoptj:=optj

44、-vi+vi*pi;end;end;end;procedure print;vari,ans:longint;beginans:=0;for i:=1 to n doif optians thenans:=opti;writeln(ans-1);end;begininit;main;print;end.金明的预算方案(budget.pas/c/cpp)来源： NOIP2006 第二题【问题描述】金明今天很开心， 家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是， 妈妈昨天对他说： “你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N 元钱就行”。今天一

45、早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：主件 附件电脑 打印机，扫描仪书柜 图书书桌 台灯，文具工作椅无如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有0 个、1 个或 2 个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的N 元。于是，他把每件物品规定了一个重要度，分为5 等：用整数 15 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是10 元的整数倍）。他希望在不超过N 元（可以等于N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第 j 件物

46、品的价格为vj ，重要度为wj ，共选中了k 件物品，编号依次为j1，j2，, ，jk，则所求的总和为：vj1*wj1+vj2*wj2+ ,+vjk*wjk。（其中 *为乘号）请你帮助金明设计一个满足要求的购物单。【输入文件】输入文件 budget.in 的第 1 行，为两个正整数，用一个空格隔开：N m（其中 N（32000）表示总钱数，m（60）为希望购买物品的个数。）从第 2 行到第 m+1 行，第 j 行给出了编号为j-1 的物品的基本数据，每行有3 个非负整数：v p q（其中 v 表示该物品的价格（v0，表示该物品为附件，q 是所属主件的编号）【输出文件】名师资料总结 - - -精

47、品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 36 页 - - - - - - - - - 输出文件 budget.out 只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（=0)and(fj-ai.v0+ai.w0fj) then fj:=fj-ai.v0+ai.w0;名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 36 页 - - - - - -

48、 - - - if (j-ai.v0-ai.v1=0)and(fj-ai.v0-ai.v1+ai.w0+ai.w1fj) thenfj:=fj-ai.v0-ai.v1+ai.w0+ai.w1;if (j-ai.v0-ai.v2=0)and(fj-ai.v0-ai.v2+ai.w0+ai.w2fj) thenfj:=fj-ai.v0-ai.v2+ai.w0+ai.w2;if (j-ai.v0-ai.v1-ai.v2=0)and(fj-ai.v0-ai.v1-ai.v2+ai.w0+ai.w1+ai.w2fj) thenfj:=fj-ai.v0-ai.v1-ai.v2+ai.w0+ai.w1+ai

49、.w2;end;max:=0;for i:=1 to n do if fimax then max:=fi;writeln(max*10);end.背包问题方案的求法和大多数 DP 问题的方案的求法一样，增加一个数组path 和状态维数相同用来记录当前状态的决策就OK 了。输出方案时候通过当前决策推出上一决策，这一连穿的决策序列就是要求的方案。下面看这样一个数据：载重： 6 物品个数： 3重量价值物品 1： 3 10 物品 2： 2 2物品 3： 1 9一维状态求解过程：i=1 : (枚举物品 )opt0.6= 1 0 0 11 0 0 0path0.6=0 0 0 1 0 0 0 记录最后装

50、入包中的物品的编号i=2opt0.6=1 0 3 11 0 13 0path0.6=0 0 2 1 0 2 0i=3opt0.6=1 10 3 12 20 13 22path0.6=0 3 2 3 3 2 3二维状态求解过程：（略）可以看到一维状态的最优解是正确的，但细心分析发现一个惊人的问题：方案不对！什么最优解正确而方案不正确呢？因为在解 i=3 时 opt6 用到的方案数应该是9+2+10=21。 显然这个方案是真确的，所以最优解正确。 但是求解完opt6 后，接着求解 opt3却把原来的opt3=10 改成了 opt3=2+9=11 这样，在整个求解过程结束后最后的方案opt6=9+2