网上找一些-动态算法

2、递归地定义最优值（写出动态规划方程2、子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反对fn1(xn1)初始化 {边界条件fork:=ndownto1for每一个xk∈Xkforuk∈Uk(xkdo {∞或xk t:=φ(fk1(xk iftfk(xkthenfk(xk):=t;{计算fk(xk)的最优值}t:=一个极值 {∞或for每一个x1∈X1iff1(x1)比t更优then <!--#EndEditable--不同．描述阶段的变量称为阶段变量。在多数情况下，阶段变量是离散的，用k面的例子中，第一个阶段就是点A，而第二个阶段就是点A到点B，第三个阶段是点B到点C，而第四个阶段是点C到点D。状态：状态表示每个阶段开始的自然状况或客观条件，它不以人们的意志为转移，也称为不可控面的例子中，第一个阶段有一个状态即A，而第二个阶段有两个状态B1和B2，第三个阶段是三个状态C1，C2和C3，而第四个阶段又是一个状态D。无后效性：要求状态具有下面的性质：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。换句话程的每一次实现x(k+1)x(k)ku(k)的值变化而变化，那么可以把这一关系看成最优性原理:实际上是要求问题的最优策略的子策略也是最优。让通过对前面的例子再分析来具体说明这一点：从A到D，知道，最短路径是AàB1àC2àD，这些点的选择构成了这个例子的最优策略，根的最短路径……──事实正是如此，因此认为这个例子满足最优性原理的要求。现有一图G，求从起点VsVe的最短距离。设：VjVsVjM(i,j)───Vi到Vj的非负长度。↓Vs↓ | | | （Vk与Vj之间相连 | Sj小于 ||Y|N|||-------------------|||↓||H（j）←Vk 注意：1.2.只有队列的首结点是目标结点时，才可停止计算。否则得出的不一定是最优解。N*N(<=100)M，M[A1，B1]开始到M[A2，B2]结束的相邻项序列.两个项M[I，J]和M[K，L]相邻的件是指满足如下情况之一：I=K+-1I=KJ=L+-1任务：从文件中输入矩阵MK(K<=4)M[A1，B1]M[A2，B2]的值。对于每一组M[A1，B1]和M[A2，B2]，求一相邻项序列，使得相邻的绝对值之和为最小。49612───每行N个数据，共N87359117324114A1,B1A2,B2K行223117───第一组数据相邻的绝对值之和的最小值47911两个顶点的最短路问题。设：Sum[I,J]为从起点VsM[I,J]的最短距离。H[I,J]记录结点M[I,J]的前趋结点。LProgramgconstfang:array[1..4,1..2]ofinteger=((-1,0),(0,-sum:Array[1..100,1..100]ofinteger;m:Array[1..100,1..100]ofinteger;h:Array[1..100,1..100,1..2]ofbyte;procedurec:array[1..100]ofinteger;

flag:=true;a:=1;c[a]:=m[x2,y2];x:=x2;y:=y2;whileflagdo

a:=a+1;x3:=x;y3:=y;x:=h[x3,y3,1];y:=h[x3,y3,2];if(x=x1)and(y=y1)thenflag:=false; {求出整条路径，放入数组C中}wrin(f2,zz,'',sum[x2,y2]);forb:=adownto1dowrite(f2,c[b],'');{打印结果}wrin(f2);procedureadd(x,y,i:integer;<I>var</I>

newe^.x:=x;ifi=0thenl^.next:=e{加入队列}elsebeginf:=l;g:=f^.next;flag:=true;fora:=1toidoifsum[g^.x,g^.y]>sum[x,y]thene^.next:=g;f^.next:=e;flag:=false;a:=i;

f:=f^.next;

ifflagthenf^.next:=e;{加入队列}procedure

fillchar(sum,sizeof(sum),255);Sum1}sum[xz,yz]:=0;{置起点Sum值为0}new(e);e^.x:=xz;new(l);l^.next:=e;c:=1;{现在队列结点个数}whileflagdov:=l^.next;dispose(l);{取出首结点l:=v;c:=c-1;{指针下移一位，结点个数减一}x:=v^.x;y:=v^.y;if(x=x2)and(y=y2)thenflag:=false;ifflagthenfora:=1to4do 1)

if(x1>0)and(x1<=n)and(y1>0)andsj:=sum[x,y]+abs(m[x,y]-if(sj<sum[x1,y1])orh[x1,y1,1]:=x;add(x1,y1,c,l);c:=c+1;{结点个数加一}

assign(f1,'gassign(f2,'g974.out');reset(f1);rewrite(f2);readln(f1,n);fora:=1tondoforb:=1tonread(f1,m[a,b]);readln(f1);end;{读入数组}readln(f1,k);fora:=1tokdo

readln(F1,x1,y1,x2,y2);{读入任务}态的转移,一个决策序列就是在变化的状态中产生出来的,故有"动态"的含义,称这种解决多阶段决策Catcher防卫(Gprograma:array[1..4000]ofinteger;{高度数组}c:array[1..4000,1..2]ofinteger;procedurereadfile;assign(f,'catcher.dat');reset(f);fori:=1tonumdoprocedurework;fillchar(c,sizeof(c),0);c[num,1]:=1;fori:=num-1downto1don:=0;forj:=i+1tonumif(a[i]>a[j])and(max<1+c[j,1])thenbeginn:=j;max:=1+c[j,1];end;c[i,1]:=max;c[i,2]:=n;wrin;wrin('Max:',max);{打印最大值}max:=0;n:=0;fori:=1tonumifc[i,1]>maxthenbeginmax:=c[i,1];n:=i;wrin(n,'');n:=c[n,2];untiln=0;readfile;work;Perform巡回演出(FlutePhlharmoniker乐团2000准备到Harp做一次大型演出,本着普及古典音乐的目的,乐团指Harp(2,3,...n)n-12(1,3,4...n)的航班,如此下去.应的两个城市的航班的价格,价格为零表示那天两个城市之间没有航班.例如"375080"表示第一75KOI,80KOI75KOI,第五天没有航班,如此循环.输入文件由n=k=0的场景结束.36213037507120110010011012046070603023201000初看这道题,很容易便可以想到动态规划,因为第xyx-1规划的无后效性原则,即只与上一个状态相关联,而某一天xS=C[(x-1)modm+1].值,C[i,j,l]ij城市间第lA[i,j]=Min{A[i-1,l]+C[l,j,i](l=1..nprograma:array[1..1000,1..10]ofinteger;c:array[1..10,1..10]ofrecord{航班价格数组}t:array[1..30]ofinteger;e:array[1..1000]ofinteger;procedurework;fori:=1tondoifthena[1,i]:=c[1,i].t[1];fori:=2tokdoforj:=1tondoforl:=1tondoifand(c[l,j].t[(i-1)modc[l,j].num+1]<>0)and((a[i,j]=0)or(a[i-1,l]+c[l,j].t[(i-1)modc[l,j].num+1]<a[i,j]))thena[i,j]:=a[i-1,l]+c[l,j].t[(i-1)modc[l,j].num+1];{赋值}e[p]:=a[k,n];pprocedurereadfile;assign(f,'PERFORM.DAT');reset(f);assign(fout,'PERFORM.OUT');rewrite(fout);readln(f,n,k);p:=0;while(n<>0)and(k<>0)dofori:=1tondoforj:=1toi-1doforl:=1toc[i,j].numdoforj:=i+1tondoforl:=1toc[i,j].numdofori:=1top-1do且同时求出了到中间状态的最优值,这对于很多实际问题来说是很有用的.这几年,动态规划已在市信少.(G''99则F[I,J]=Min{Max{F[i-1,k],Sum[k+1,J]}}1<=k<=j-（GDKOI'2000对于任意一个整数数列，可以在每两个整数中间任意放一个符号‘+’或‘-’，这样就可以可以构造8个表达式：17+5+(-17+5+(-21)-17+5-(-17+5-(-21)-17-5+(-17-5+(-21)-15=-17-5-(-17-5-(-21)-对于一个整数数列来说，能通过如上的方法构造不同的表达式，从而得到不同的数值，如果该数值能够被k。在上面的例子中，该数列能717+5+(-21)-15=-14)，但不能被5。现在数据存放在当 文件的第一行是一个整数M，表示有Mm每个子任务有两行。第一行是两n和K（1<=n<=1000,2<=k<=100），n和k中间有一个空格。n数列中整数的个数；k是需要你判kn间用空格隔开，每个整数的绝对值都不超过10000。答案输出到当 "Divisible"，否则输出"NotDivisible"│输入文件：div．in│输出文件：div．out ││4 │Not││175-21 │4 │175-21 根据同余的性质注意到[(Amodk)+B]modk=(A+B)modFalseF[i-F[i][(data[i]+v)modTrueF[i-第二行N个数,为Ｎ种物品重量；两个数用空格分隔；第三行NN4234713592141后，对应的子问题中的重复，这样就将重复地求解；在第一次遇到重复时把它解决，并将解保存起来，以备后面。动态规划法常用来求一个问题在某种意义下的最优解。--译者）则F[i]={maxing 当F[i-weigh[k]]=maxMax{F[i-weigh[k]]+worth[k]}F[i-weigh[k]]>0用带奶的总时间。找到这样一组歌曲的集合，使得歌曲的总长度不超过给Bessie挤奶的总时间且使Bessie的合的值的和最大，且其尺寸的和受某些限制所约束。集合中任何一个特定的项目的总数目/尺寸过的背包是一只水桶，取0.473升的原油，0,263升的飞机和0,264升的煤油就是有意义的。这是形式N复杂度是O(N2)。否比当前最好的大小为K+S的背包更符合条件。一个语言L，如果有一架非确定图灵机MP(nInw，MP(n)w，则称LNPL损失的条件下，缩短数字（如果你有3,5个物品，你可以仅用3）。如果值都是同一个，那么如果能被放入所有背包中的物品的最大值是n，则存在使用n个最小物品的分数膨胀[1998USACONational栏[1999USACOSpring各种长度的木板（至多50个）。已知木材店木板的长度，要的围栏长度，计算建所用的围你在Beaver郡中部一百英里有一个的城市中，想将你的油箱装满好能到达RitaBlanca。幸运地是，这个小镇有两三个，但它们的油像要用光了。已知每个的油价，每个的油量，计算为了花最少的钱，应该从每个买多少。分析：这是一个小数背包问题，背包是油箱，物品是。3A，B，C010x，y，z，使得A(x)+B(y)+C(z)为最大，并且满足x2+y2+z2〈ＮX0123456789A(x)24711131518221815B(x)5 53C(x)81217在一个圆形操场的四周摆放着N堆石子(N<=100),现要将石子有次序地合并成一堆.规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分.编一程序,由文件读入堆栈数N(!)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最小;(2)选择一种合并石子的方案,使用权得做N－1次合并,得分的总和最大;从第一N行为得分最小的合并方案.第N+1行是空行.从第N+2行到第2N+1行是得分最大合并方案.每种合并方案N行表示,其i行(1<=i<=N)表示第i次合并前各堆的石子数(依顺时针次序输出,哪一堆44 ９－８－５ 设有一排数，共ｎ个，例如：22 .任意2个相邻的数可以进行归并归并的代价为该两个数的和,经过不断的归并,最后归为一堆,而全部归并代价的和称为总代价,给出一种归并算法,使总代价为最小.412 2ICU(ICU是信息学竞赛的货币的单位）;一个花瓶的价格是5ICU。为了吸引的顾客，商店提供了特殊价。特殊商品是把一种或几种商品分成一组。并降价销售。例如:365ICU;2110ICU12ICU编一个程序，计算某个顾客所购商品应付的费用。要充分利用价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用价如上所述，并且某顾客物品为:3朵花和2个花瓶。那么顾客应付款为14ICU1朵花加2个花瓶:价:102朵花正常价:4商店提供的商品及价格（文件名为OFFER．TXT）。两个文件中都只用整数。行，每行中含3个数C，K，P。C代表商品的编码（每种商品有一个唯一的编码），1≤C≤999。K代表该种商品总数，1≤K≤5。P是该种商品的正常单价（每件商品的价格），1≤P≤999。请注意，购物筐中最多可放5*5＝25件商品。第二个文件OFFER．TXT的格式为:第一行是一个数字S（0≤S≤99），表示共有S种。下面共S行，每一行描述一种商品的组合品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1≤C≤999。K代表该种商品在此组合中的数量，1≤K≤5。本行最后一个数字P（1≤P≤9999）代表此商品组合的价。当然，价要低于该组合品正常价之总和。OUTPUT．TXT（占一行），（输入文件指明所购商│││ ││2││││││７３２││175│││││８２５││27│82│└────────┘的序列，对于给定的基元的集合P，如果可以从中选出N个基元P1，P2，…Pn，将它们各自对应的字符串依次联接后得到一个字符串S，称S可以由基元集合P字符串的前K个字符称为该字符串的前缀，其长度为K.请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，INPUT.TXT文件DATA.TXT描述要处理的字符串T，每一行行首有一个大写英文字母，算法：动态规划题型：II型难度：4编程时间：4旅游有如下规则计算精确到分（1元=100分）。编写程序估计实际行驶在某路线所需的最小费用。 答案输出到当 输入文件 输出文件 38.0915.722.120.87 1、每艘船在出发的一瞬间提交航行计划（提交和出发的时间差可以忽略23（两港口间的直达航线）上只能有一艘船，因此，一艘船在出发的瞬间发现某航45674234523：45，速度单位用节（海里/小时）表示。在计算时间时，中间结果应从当前下的文本文件“LANE.DAT”读入数据。输入的数据一定有解，且不会出现00：00的情第三行开始NNXNN（单位为海里），整数间以空格分隔（若为0表示两港口没有直达航线相连）；答案输出到当前下的文本文件“LANE.OUT3输入文件 输出文件 0 0 00 0 0 04 行n，侍卫所需的经费k，该边的儿子数m，接下来m个数，分别是这个节点的m个儿子的标号 对于一个n（0<n<=1500）1nSramoc(K,M)表示用数字0、1、２…、K-1MK、M，Sramoc(K,M)。例如K=2，M=7，Sramoc(2,7)=1001。Sramoc(K,M)到SRAMOC.OUT。7Timelimit:1Seconds Memorylimit:32768KTotalSubmit:843 AcceptedSubmit:303用它的数字乘以它左边和右边的数，所以不允许拿第1张和最后1张牌。最后一次移动后，这里只剩下两10150205，1、20、50，6Timelimit:1Seconds Memorylimit:32768KTotalSubmit:172 AcceptedSubmit:4534510900旅行家来到了一个著名的旅游胜地。这里的风景很好，旅行家想自己把所有的路都走一遍，这样可以这个旅游胜地一共有n同的标准。现在请你写一个程序，为旅行家设计一条路线，使得这条路线覆盖尽可能多的道路（不包括乘车经过的），输入包括了多个测试数据。每个测试数据开头是一个整数n（1<=n<=100），表示路口总数。接下来一行包括了n数m，表示道路总数。之后的m行包括两个整数x，y（1<=x，y<=n）分别表示该道路连接的两个路口。路口按照输入顺序从小到大依次编5358761213152534356邀请 。但是，正如你所知，比较傲慢，而且不能 每一组的第一行有整数N（<=300）和M（<=5000）。以下的N行是N个 的名字，都不超过10个字符，而且中间不含空格。接下来的M行是列举有的，每行有2个 输出文件 行输出一个整数，表示第i组有多少位 。第2i+1行输出第I组的名字，用空格分开。你可以假设一定要将这些分成4组，不能比4组少。4AAABBC6AAABBCDCase1Case2A1D时间限制：100ms农民有如下型号的牛奶容器：10，2，1，1/4，1/8，1/16。编写一个程序能计算用这些容器取X牛奶共有多少不同方法。在所有的数据中，X都是整数且5 .正在玩军事，现在他有N个洲际。他需要在最短的时间内，用这N个洲际摧毁敌方N个目标，1个洲际只能摧毁1个目标。觉得给每个洲际确定目标是一件很麻烦的事情。请你编程帮助给每个洲际确定目标，使每个洲际到其目标的距离之和为最小。第一行为N(N≤12)第2行到N+1行，每一行包含一个坐标(X,Y)，表示一个洲际的位置。N+22N+1X,Y)，表示一个目标的位置。其中-10000≤X,Y≤10000，X,Y为整数。1-1--2-2寻找在宇宙中居住的方法。找到合适的居住环境是一题，因为宇宙中充满着各种各样的，比如在某个区域内经常有小行星或陨石出没（这些都称作飞行物）。科学家们经过观察发现飞行物的飞行轨迹要么互相平行要么互相垂直（在三中）。所以可以把宇宙看作是许多等大的正方体格子所组成的大长方体，凡是有飞行物经过的格子都不是理想的居住地。现在给你宇宙空间的大小和飞行物的飞行轨迹，请你编程帮助科学家们找到一个最大的理想居住地，且这个居住地是一个正方体。输入以下有N行，每一行为：kind,x,y,z,t。例如：x13y1232(1,2,3z1231(1,2,3)到(1,2,1)0≤N≤100。0<x0,y0,z0≤20且x0,y0,z0-x0≤x≤x0;-y0≤y≤y0;-z0≤z≤z0;且x,y,z当kind为x时，-x0≤t≤x0输出文件时间限制：2秒10103x-100y0-0z0010-10不过，这个医生在开药方的时候，有一个固定的标准模式。他有一个药材库，里面有n种用n1，2，……nn现在，有一个关于这个医生的药方，药方中写有P整数p，表示具体的一个药方的药的数目。继续下来的p行，每行有一个整数，表示这个药方第i个药被鉴别出是k；如果k0，表示这个药还没有鉴别出来。输出文件的第一行是一个整数m，表示总共可以构造出mm5241352312403002235435从文件l计算日费用的最小值l结果写入文件文件BOR。IN第一行的整数N表示城市的个数，5<=N<=10000(假定城市都是沿高速公路编号，相邻的城市也紧接。城市一与城市N相邻）。接下来的N行每行为俩个用单个空格隔开的非负的距离（用英里做度量）10000001000612231252123Squares（正方形TimeLimit:0.5secondMemoryLimit:1000K给出N(0<N<100)个正方形和点P.点P和正方形的最短线段是指点P线或区域的最短连线。如果P在正方形，那么它们之间的距离为0.有些正方形的的顶点是重第一行为数N.接下来的N行包含有4个整数，范围在(-9999,9999).前2个表示一个顶点的X,YPx，y序给出的。当有两个正方形到点P的距离是相等时，序号小的先输出。当比较距离时，请用1E-14SampleInput00103100Sample1PensilsandCircles(铅笔和圆）TimeLimit:1secondMemoryLimit:一个老和一个老坐在桌子上写信。在桌子上有N只铅笔，用坐标(xi,yi)表示。铅笔的直3<=N<=5000.n你必须输出圆经过的三支铅笔的坐标。在圆内有(N-3)/2支铅笔，在圆外也有(N-3)/2支铅笔。若没有解决方案，输出"Nosolution".若有多种解决方案，则任输出一种。SampleInput00102-211102-3-Sample012TimeLimit:1secondMemoryLimit:1000KAB接下来的就是地铁的描述。第一行为一整数N，它是地铁站的数量。假设N不超过200N行，每行包含两个浮点数(第i-行为第i-个地铁站的坐标)。接下来的描述表示哪两个站相连，每一最后为点A和B的坐标，一行一个。第一个为的地铁站的数量，后跟着一系列地铁站的Sample1400109099121324001010SampleOutput4421车厢顺序，当输入行的第一个数为0，表示文件结束。432060TimeLimit:2在罗马尼亚，有K个无线电发射站，位于不同的地方和海拔高度。每个站都有一定的辐射范围，也就是说，可以发射信号的最远距离。想在某地建一个接收站，以使它能够接收所有K个发射站的信罗马尼亚被划分成M*N个矩阵，i行和j列的值表示的是相应区域的海拔高度。矩阵的小方格的边长为1.所有的K个发射站位于地图上的不同的坐标并且和相应区域的海拔高度是一样的你的任务是计算建接收站可以有多少种方案（可能）。注意：如果接收站位于行i和列j，海拔高度为h1和h2(h1<>h2),这就算两种不同的方案。M,N(1<=M,N<=50) K(1<=K<=min(,1000)),