动态规划算法.doc

动态规划（一）、动态规划的基本思想：动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。二、设计动态规划法的步骤：1、找出最优解的性质，并刻画其结构特征；2、递归地定义最优值（写出动态规划方程）；3、以自底向上的方式计算出最优值；4、根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构造最优解。三、动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。（二）、动态规划算法的基本步骤设计一个标准的动态规划算法，通常可按以下几个步骤进行： 1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。 2. 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 3. 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 4. 写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下： 标准动态规划的基本框架frame1. 对fn+1(xn+1)初始化; 边界条件2. for k:=n downto 1 do 3. for 每一个xkXk do4. for 每一个ukUk(xk) do begin5. 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 每一个x1X1 do11. if f1(x1)比t更优 then t:=f1(x1); 按照10式求出最优指标12. 输出t;但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行： 1. 分析最优解的性质，并刻划其结构特征。 2. 递归地定义最优值。 3. 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 4. 根据计算最优值时得到的信息，构造一个最优解。 步骤(1)-(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。 （三）、动态规划概述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）0Vs进入队列L-移出队列L的队首Vk-|Vk是不是Ve-|-计算结束打印路径|NY|由Vk扩展出结点Vj|（Vk与Vj之间相连）|SjSum(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，存在从MA1，B1开始到MA2，B2结束的相邻项序列.两个项MI，J和MK，L相邻的件是指满足如下情况之一：(1)I=K+-1和J=L(2)I=K和J=L+-1。任务：从文件中输入矩阵M，再读入K(K=4)组MA1，B1和MA2，B2的值。对于每一组MA1，B1和MA2，B2，求一相邻项序列，使得相邻项之差的绝对值之和为最小。输入格式：4N19612每行N个数据，共N行873559111173262K4114表示A1,B1和A2,B2的值，共K行2234输出格式：117第一组数据相邻项之差的绝对值之和的最小值是1775879612第一组数据的相邻项序列24791111解析：本题若将相邻的两个数看作是两个顶点，两个数之差的绝对值作为权，则问题转化成求两个顶点的最短路问题。设：SumI,J为从起点Vs到结点MI,J的最短距离。HI,J记录结点MI,J的前趋结点。L为记录待扩展的结点的队列。鉴于数组进行排序时速度较慢，所以用链表作为记录结点的队列的类型，适于排序。参考程序：Programgdoi974;constfang:array1.4,1.2ofinteger=(-1,0),(0,-1),(1,0),(0,1);上下左右四个方向type定义POINT类型,其中X,Y为结点在矩阵中的坐标,NEXT为队列中的后继结点point=note;note=recordx,y:byte;next:point;end;varsum:Array1.100,1.100ofinteger;m:Array1.100,1.100ofinteger;h:Array1.100,1.100,1.2ofbyte;f1,f2:text;a,b,x1,y1,x2,y2,n,k,zz:integer;procedureprint;vara,b,x,y,x3,y3:integer;c:array1.100ofinteger;flag:boolean;beginflag:=true;a:=1;ca:=mx2,y2;x:=x2;y:=y2;whileflagdobegina:=a+1;x3:=x;y3:=y;x:=hx3,y3,1;y:=hx3,y3,2;ca:=mx,y;if(x=x1)and(y=y1)thenflag:=false;end;求出整条路径，放入数组C中writeln(f2,zz,sumx2,y2);forb:=adownto1dowrite(f2,cb,);打印结果writeln(f2);end;procedureadd(x,y,i:integer;varl:point);vare,f,g:point;a,b,c:integer;flag:boolean;beginnew(e);e.x:=x;e.y:=y;ifi=0thenl.next:=e加入队列elsebeginf:=l;g:=f.next;flag:=true;fora:=1toidobeginifsumg.x,g.ysumx,ythenbegine.next:=g;f.next:=e;flag:=false;a:=i;加入队列end;f:=f.next;g:=f.next;end;ifflagthenf.next:=e;加入队列end;end;proceduretry(xz,yz:byte);vara,b,c,sj,x,y,x1,y1:integer;e,l,v:point;flag:boolean;beginfillchar(sum,sizeof(sum),255);置Sum值为-1sumxz,yz:=0;置起点Sum值为0flag:=true;new(e);e.x:=xz;e.y:=yz;new(l);l.next:=e;起点进入队列c:=1;现在队列结点个数whileflagdobeginv:=l.next;dispose(l);取出首结点Vl:=v;c:=c-1;指针下移一位，结点个数减一x:=v.x;y:=v.y;if(x=x2)and(y=y2)thenflag:=false;若为目标结点，则结束计算ifflagthenbeginfora:=1to4do向四个方向扩展beginx1:=x+fanga,1;y1:=y+fanga,2;if(x10)and(x10)and(y1=n)thenbeginsj:=sumx,y+abs(mx,y-mx1,y1);if(sjsumx1,y1)or(sumx1,y1=-1)thenbeginsumx1,y1:=sj;hx1,y1,1:=x;hx1,y1,2:=y;记录路径add(x1,y1,c,l);将新扩展出来的结点进入队列c:=c+1;结点个数加一end;end;end;end;end;print;打印结果end;Beginassign(f1,gdoi974.dat);assign(f2,gdoi974.out);reset(f1);rewrite(f2);readln(f1,n);fora:=1tondobeginforb:=1tondoread(f1,ma,b);readln(f1);end;读入数组readln(f1,k);fora:=1tokdobeginzz:=a;readln(F1,x1,y1,x2,y2);读入任务try(x1,y1);end;close(f1);close(f2);End.四、小结综上所述，标号法是动态规划的一种，它采用顺推的方法，对图的每一边检测一次，没有重复的回溯搜索，要比一般的搜索优秀得多。它是一种最佳算法。（六）、动态规划教程一.动态规划含义:在现实生活中,有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都要做出决策,从而使整个过程达到最好的活动效果.因此,各个阶段决策确定后,组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程,就称为多阶段决策过程,这种问题称为多阶段决策问题.在多阶段决策问题中,各个阶段采取的决策,一般来说是和时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有动态的含义,我们称这种解决多阶段决策最优化的过程为动态规划.二.动态规划特征动态规划的显著特征是:无后效性,有边界条件,且一般划分为很明显的阶段.动态规划一般还存在一条或多条状态转移方程. 三.例题1.Catcher防卫导弹(GDOI98)题目讲得很麻烦,归根结底就是求一整串数中的最长不上升序列这道题目一开始我使用回溯算法,大概可以拿到1/3的分吧,后来发现这其实是动态规划算法中最基础的题目,用一个二维数组C1.Max,1.2来建立动态规划状态转移方程(注:C1.Max,1表示当前状态最多可击落的导弹数,C1.Max,2表示当前状态的前继标志):Ci=MaxCj+1,(j=i+1.n),然后程序也就不难实现了.示范程序:programcatcher_hh;varf:text;i,j,k,max,n,num:integer;a:array1.4000ofinteger;导弹高度数组c:array1.4000,1.2ofinteger;动态规划数组procedurereadfile;beginassign(f,catcher.dat);reset(f);readln(f,num);fori:=1tonumdoreadln(f,ai);end;procedurework;beginfillchar(c,sizeof(c),0);cnum,1:=1;清空数组,赋初值开始进行动态规划fori:=num-1downto1dobeginn:=0;max:=1;forj:=i+1tonumdoif(aiaj)and(maxmaxthenbeginmax:=ci,1;n:=i;end;返回寻找路径repeatwriteln(n,);n:=cn,2;untiln=0;end;beginreadfile;work;end.2.Perform巡回演出(GDKOI2000)题目描述: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天对应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如375080表示第一天机票价格是75KOI,第二天没有航班,第三天的机票是80KOI,然后循环:第四天又是75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.输出:对每个场景如果乐团可能从城市1出发,每天都要飞往另一个城市,最后(经过k天)抵达城市n,则输出这k个航班价格之和的最小值.如果不可能存在这样的巡回演出路线,输出0.样例输入:362130150375080712011001001101200460706050301351402708023207018000样例输出:4600初看这道题,很容易便可以想到动态规划,因为第x天在第y个地方的最优值只与第x-1天有关,符合动态规划的无后效性原则,即只与上一个状态相关联,而某一天x航班价格不难求出S=C(x-1)modm+1.我们用天数和地点来规划用一个数组A1.1000,1.10来存储,Ai,j表示第i天到达第j个城市的最优值,Ci,j,l表示i城市与j城市间第l天航班价格,则Ai,j=MinAi-1,l+Cl,j,i(l=1.n且Cl,j,i0),动态规划方程一出,尽可以放怀大笑了.示范程序:programperform_hh;varf,fout:text;p,l,i,j,n,k:integer;a:array1.1000,1.10ofinteger;动态规划数组c:array1.10,1.10ofrecord航班价格数组num:integer;t:array1.30ofinteger;end;e:array1.1000ofinteger;procedurework;begin人工赋第一天各城市最优值fori:=1tondobeginifc1,i.t10thena1,i:=c1,i.t1;end;fori:=2tokdobeginforj:=1tondobeginforl:=1tondobeginif(jl)and(cl,j.t(i-1)modcl,j.num+10)判断存在航班and(ai,j=0)or(ai-1,l+cl,j.t(i-1)modcl,j.num+1ai,j)判断比当前解优thenai,j:=ai-1,l+cl,j.t(i-1)modcl,j.num+1;赋值end;end;end;ep:=ak,n;第p个场景的最优值end;procedurereadfile;读文件beginassign(f,PERFORM.DAT);reset(f);assign(fout,PERFORM.OUT);rewrite(fout);readln(f,n,k);p:=0;while(n0)and(k0)dobeginp:=p+1;fillchar(c,sizeof(c),0);fillchar(a,sizeof(a),0);fori:=1tondobeginforj:=1toi-1dobeginread(f,ci,j.num);forl:=1toci,j.numdoread(f,ci,j.tl);end;forj:=i+1tondobeginread(f,ci,j.num);forl:=1toci,j.numdoread(f,ci,j.tl);end;end;work;readln(f,n,k);end;输出各个场景的解fori:=1top-1dowriteln(fout,ei);write(fout,ep);close(f);close(fout);end;beginreadfile;end.四.小结动态规划与穷举法相比,大大减少了计算量,丰富了计算结果,不仅求出了当前状态到目标状态的最优值,而且同时求出了到中间状态的最优值,这对于很多实际问题来说是很有用的.这几年,动态规划已在各省市信息学奥林匹克竞赛中占据相当重要的地位,每年省赛8道题目中一般有23道题目属于动态规划,动态规划相比一般穷举也存在一定缺点:空间占据过多,但对于空间需求量不大的题目来说,动态规划无疑是最佳方法!五.课后题目1.m个人抄n本书,每本书页数已知,每个人(第一个人除外)都必须从上一个人抄的最后一本书的下一本抄起(书必须整本整本的抄),求一种分配方法,使抄书页数最多的人抄书页数尽可能少.(GDOI99Books).2.有一字符串有多种编码方式可供人选择，将这个字符串进行编码，使求得得编码长度最短。（GDKOI2000Compress)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。首行行末应没有空格。*输入输出样例：输入文件：divin 输出文件：divout2 Divisible 4 7 Not Divisible 17 5 -21 15 4 5 17 5 -21 15 2.背包问题 设有种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为，今从种物品中选取若干件（同一种物品可以多次选取），使其重量的和小于等于，而价值的和为最大。输入数据：第一行两个数：物品总数，背包载重量；两个数用空格分隔；第二行N个数,为种物品重量；两个数用空格分隔；第三行N个数,为N种物品价值;两个数用空格分隔；输出数据：第一行总价值；以下N行，每行两个数，分别为选取物品的编号及数量；输入样例：41023471359输出样例：122141前提贪心法（它是一种多步决策法，它总是作出在当前看来是最好的选择，它的考虑不是从整体出发，而只是某种意义上的局部最优，这样贪心法不能对所有问题达到整体最优解，但是对相当范围的许多问题都能够产生整体最优解。-译者）动态规划（它是将问题进行逐步的划分来缩小问题的规模，直到可以求出子问题的解为止。分划子问题后，对应的子问题中含有大量的重复，这样就将重复地求解；在第一次遇到重复时把它解决，并将解保存起来，以备后面引用。动态规划法常用来求一个问题在某种意义下的最优解。-译者）递归下降3.用录音带录音农场主约翰最喜欢的爱好是制作一个Bessie喜欢的音乐合集磁带以便它在产奶时听。Bessie的产奶量取决于它产奶时所听的歌曲。已知一组歌曲（每首歌都由一对整数此曲的长度（以秒计），听该首歌时的产奶量来表示）以及给挤奶的总时间。找到这样一组歌曲的集合，使得歌曲的总长度不超过给Bessie挤奶的总时间且使Bessie的产奶量达到最大。抽象描述已知一组物品-每个都有其尺寸和值（比如，重量），以及可用的总空间。找到这样一个集合，使得该集合的值的和最大，且其尺寸的和受某些限制所约束。集合中任何一个特定的项目的总数目/尺寸不能超过它的可利用率。解题想法视其为背包问题的一般方法是一个容量受限的背包使得放入其中的物品的值达到最大。以上述问题为例，Bessie产奶时听的音乐带就是“背包”，而那些歌就是“放入背包中的物品”。4.三个背包问题背包问题有三种形式：小数背包问题允许将小数表示的物品放入背包中的是小数背包问题。举例来说，如果物品是原油、飞机燃料、煤油而你的背包是一只水桶，取0.473升的原油，0,263升的飞机燃料和0,264升的煤油就是有意义的。这是形式最简单的要解决的背包问题。整数背包问题在整数背包问题中，只有完整的物品能放入背包里。此形式的一个例子就是：部分的曲子不允许放入包中。多重背包问题在多重背包问题中，需被填充的背包多于一个。如果允许有小数的物品放入，也就等于有一个大的背包，其容量相当于所有可用背包的和。因此，此术语只用来指多重整数背包的情况。小数背包问题小数背包问题是三者中最简单的，其贪婪解法如下：找到“值密度”（物品值/尺寸）最大的物品如果总容量仍就超过物品的可利用率，把所有满足条件的物品放入背包中，然后反复执行。如果总容量少于物品的可利用率，尽可能多的使用可用空间，然后终止。由于这个算法必须先按照值密度把物品分类，然后以降序将它们放入背包，直至容量用完，该算法以N log N 级运行。通常简单些的方法不是将它们分类，而是不停地找每次不用的最大值密度，这种算法的时间复杂度是O(N 2) 。注意：对于这类问题，因为你可以做一个微小的变换使得所有的物品尺寸大小为一，且原始尺寸大小和可利用率（当然用原始尺寸大小除值）的乘积就是总容量，同时有尺寸和可利用率是很少见的。延伸：在这种情况下，物品的值和可利用率可以是实数。用这种算法处理有小数的尺寸大小也不是问题。整数背包问题这个问题有点难度，但是如果背包足够小，使用动态规划，它还是可解的。依据背包大小的最大值设计动态的程序。刷新用来表示大小为S的物品的数组，颠倒其次序，看将当前物品放入大小为K的背包中所产生的集合是否比当前最好的大小为K+S的背包更符合条件。这个算法运行K*N次，其中K是背包的大小，N是物品的可利用率义之和。如果背包太大了以至于无法分配此数组，递归下降是一种选择，即这个问题是NP完全的（给定I上的一个语言L，如果有一架非确定图灵机M和一个多项式P(n)，对任何I上的长度为n的串w，M都可以在P(n)步内确定是否接受w，则称L是非确定图灵机下多项式时间复杂性问题，简记为NP问题/语言。若L是属于NP的，且对NP中的每一个语言L，都存在一个从L至L的多项式时间转化，我们说L是NP完整的。-译者）。当然，递归下降在以小的物品填充的大背包情况下可以运行相当长的一段时间。延伸：小数的值不是问题；数组可以用实数数组来代替整数数组。小数的可利用率并不影响什么，在没有大量损失的条件下，缩短数字（如果你有3,5个物品，你可以仅用3）。小数的尺寸是个讨厌的东西，它使得问题递归下降。如果尺寸都相同，问题就能贪婪地解开，在下降的值排序中选择物品，直到背包满为止。如果值都是1.0，同样地使用贪心法，在上升的尺寸大小排序中选择物品，直到背包满为止。多重背包问题对于任何大小的多重背包，状态空间太大了以至于无法使用从整数背包算法中来的DP解法。于是递归下降是解决这个问题的方法。延伸：用递归下降，通常扩展就简单了。小数的尺寸和值就不是问题了，同样地值的计算功能也不是问题。如果值都是同一个，那么如果能被放入所有背包中的物品的最大值是n，则存在使用n个最小物品的解法。它能大大减少查找时间。5.分数膨胀1998 USACO National Championship你正试图设计一个有最高分数(10,000)的比赛。已知比赛长度，一组问题，问题的长度以及每个问题的分值，计算满足长度约束的最高分数的比赛。分析：这是一个整数背包问题，比赛是背包，尺寸是问题的长度，值是分数值。背包（比赛）尺寸的限制是其足够小使得解法在存储器中运行。6.篱笆栏1999 USACO Spring Open农场主约翰准备在他的领地建一圈篱笆。他已装好了柱子，所以他知道所要的围栏长度。当地的木材店有各种长度的木板（至多50个）。已知木材店木板的长度，约翰要的围栏长度，计算约翰建篱笆所用的围栏最大值。分析：这是个多重背包问题，木材店的木板是背包，物品是约翰用的围栏。物品的尺寸就是长度，值是一。由于值都是一，如果存在用任意K个围栏的解法，则有用K个最小围栏的解法。7.装满你的油箱你在Beaver郡中部一百英里有一个加油站的城市中，想将你的油箱装满好能到达Rita Blanca。幸运地是，这个小镇有两三个加油站，但它们的油都好像要用光了。已知每个加油站的油价，每个加油站的油量，计算为了花最少的钱，应该从每个加油站买多少汽油。分析：这是一个小数背包问题，背包是油箱，物品是汽油。动态规划问题 8.求函数最大值已知3个函数A，B，C值如下表示，自变量取值为0-10的整数。请用动态规划的方法求出一组x，y，z，使得A(x)+B(y)+C(