动态规划经典教程

  • A+
所属分类:教育文档
摘要

动态规划经典教程__引言:本人在做过一些题目后对DP有些感想,就写了这个总结:__第一节动态规划基本概念__一,动态规划三要素:阶段,状态,决策。__他们的概念到处都是,我就不多说了,我只说说我对他们的理解:__如果把动态规划的求解过程看成一个工厂的生产线,阶段就是生产某个商品的不同的环节,状态就是工件当前的形态,决策就是对工件的操作。显然不同阶段是对产品的一个前面各个状态的小结,有一个个的小结构成了最终的整个生产线。每个状态间又有关联(下一个状态是由上一个状态做了某个决策后产生的)。__下面举个例子:__要生产一批雪糕,在这个过程中要分好多环节:购买牛奶,对牛奶提纯处理,放入工厂加工,加工后的商品要包装,包装后就去销售……,这样没个环节就可以看做是一个阶段;产品在不同的时候有不同的状态,刚开始时只是白白的牛奶,进入生产后做成了各种造型,从冷冻库拿出来后就变成雪糕(由液态变成固态=_=||)。每个形态就是一个状态,那从液态变成固态经过了冰冻这一操作,这个操作就是一个决策。一个状态经过一个决策变成了另外一个状态,这个过程就是状态转移,用来描述状态转移的方程就是状态转移方程。__经过这个例子相信大家对动态规划有所了解了吧。__下面在说说我对动态规划的另外一个理解:__用图论知识理解动态规划:把动态规划中的状态抽象成一个点,在有直接关联的状态间连一条有向边,状态转移的代价就是边上的权。这样就形成了一个有向无环图AOE网(为什么无环呢?往下看)。对这个图进行拓扑排序,删除一个边后同时出现入度为0的状态在同一阶段。这样对图求最优路径就是动态规划问题的求解。__二,动态规划的适用范围__动态规划用于解决多阶段决策最优化问题,但是不是所有的最优化问题都可以用动态规划解答呢?一般在题目中出现求最优解的问题就要考虑动态规划了,但是否可以用还要满足两个条件:最优子结构(最优化原理)__无后效性__最优化原理在下面的最短路径问题中有详细的解答;__什么是无后效性呢?__就是说在状态i求解时用到状态j而状态j就解有用到状态k…状态N。__而求状态N时有用到了状态i这样求解状态的过程形成了环就没法用动态规划解答了,这也是上面用图论理解动态规划中形成的图无环的原因。__也就是说当前状态是前面状态的完美总结,现在与过去无关。。。__当然,有是换一个划分状态或阶段的方法就满足无后效性了,这样的问题仍然可以用动态规划解。三,动态规划解决问题的一般思路。__拿到多阶段决策最优化问题后,第一步要判断这个问题是否可以用动态规划解决,如果不能就要考虑搜索或贪心了。当却定问题可以用动态规划后,就要用下面介绍的方法解决问题了:__(1)模型匹配法:__最先考虑的就是这个方法了。挖掘问题的本质,如果发现问题是自己熟悉的某个基本的模型,就直接套用,但要小心其中的一些小的变动,现在考题办都是基本模型的变形套用时要小心条件,三思而后行。这些基本模型在先面的分类中将一一介绍。__(2)三要素法__仔细分析问题尝试着确定动态规划的三要素,不同问题的却定方向不同:__先确定阶段的问题:数塔问题,和走路问题(详见解题报告)__先确定状态的问题:大多数都是先确定状态的。__先确定决策的问题:背包问题。(详见解题报告)__一般都是先从比较明显的地方入手,至于怎么知道哪个明显就是经验问题了,多做题就会发现。__(3)寻找规律法:__这个方法很简单,耐心推几组数据后,看他们的规律,总结规律间的共性,有点贪心的意思。__(4)边界条件法__找到问题的边界条件,然后考虑边界条件与它的领接状态之间的关系。这个方法也很起效。__(5)放宽约束和增加约束__这个思想是在陈启锋的论文里看到的,具体内容就是给问题增加一些条件或删除一些条件使问题变的清晰。__第二节动态规划分类讨论__这里用状态维数对动态规划进行了分类:__1状态是一维的__1.1下降非降子序列问题:__问题描述:{挖掘题目的本质,一但抽象成这样的描述就可以用这个方法解}__在一个无序的序列a1_a2_a3_a4…an里,找到一个最长的序列满足:ai=aj=ak…=am_且ijk…m(最长非降子序列)或aiajak…am_且ijk…m(最长下降子序列)。__问题分析:__如果前i-1个数中用到akakai或ak=ai构成了一个的最长的序列加上第I个数ai就是前i个数中用到i的最长的序列了。那么求用到ak构成的最长的序列有要求前k-1个数中……__从上面的分析可以看出这样划分问题满足最优子结构,那满足无后效性么?显然对于第i个数时只考虑前i-1个数_显然满足无后效性,可以用动态规划解。__分析到这里动态规划的三要素就不难得出了:如果按照序列编号划分阶段,设计一个状态opt[i]表示前i个数中用到第i个数所构成的最优解。那么决策就是在前i-1个状态中找到最大的opt[j]使得ajai或aj=ai,opt[j]+1就是opt[i]的值;用方程表示为:{我习惯了这种写法,但不是状态转移方程的标准写法}__opt[i]=maxopt[j]+10=ji且aj=ai{最长非降子序列}__opt[i]=maxopt[j]+10=ji且ajai{最长下降子序列}__实现求解的部分代码:__opt[0]=maxsize;{maxsize为maxlongint或-maxlongint}__fori=1tondo__forj=0toi-1do__ifa[j]a[i]andopt[j]+1opt[i]then__opt[i]=opt[j]+1__ans=-maxlongint__fori=1tondo__ifopt[i]ansthenans=opt[i]{ans为最终解}__复杂度:从上面的实现不难看出时间复杂度为O(N2),空间复杂度O(N);__missilepasccpp来源:NOIP1999提高组第一题__某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。__输入导弹依次飞来的高度(雷达给出的高度数据是不大于30000的正整数),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。__【输入文件】missilein__单独一行列出导弹依次飞来的高度。__【输出文件】missileout__两行,分别是最多能拦截的导弹数,要拦截所有导弹最少要配备的系统数__【输入样例】__38920715530029917015865__【输出样例】__6__2__【问题分析】__有经验的选手不难看出这是一个求最长非升子序列问题,显然标准算法是动态规划。__以导弹依次飞来的顺序为阶段,设计状态opt[i]表示前i个导弹中拦截了导弹i可以拦截最多能拦截到的导弹的个数。__状态转移方程:__opt[i]=maxopt[j]+1h[i]=h[j]_0=ji{h[i]存,第i个导弹的高度}__最大的opt[i]就是最终的解。__这只解决了第一问,对于第二问最直观的方法就是求完一次opt[i]后把刚才要打的导弹去掉,在求一次opt[i]直到打完所有的导弹,但这样做就错了。__不难举出反例:61732__错解:63217正解:61732__其实认真分析一下题就回发现:每一个导弹最终的结果都是要被打的,如果它后面有一个比它高的导弹,那打它的这个装臵无论如何也不能打那个导弹了,经过这么一分析,这个问题便抽象成在已知序列里找最长上升序列的问题。__求最长上升序列和上面说的求最长非升序列是一样的,这里就不多说了。__复杂度:时间复杂度为O(N2),空间复杂度为O(N)。__【源代码】__programmissileuntilseekeofifa[j]a[i]andconstendopt[j]+1opt[i]then__fin=missileinproceduremainopt[i]=opt[j]+1__fout=missileoutvaranstime=0__maxn=10000i_jlongintfori=1tondo__varbeginifopt[i]anstimethen__a_optarray[0maxn]offillcharopt_sizeofopt_0anstime=opt[i]__longinta[0]=maxlongintend__n_anslen_anstimelongintfori=1tondoprocedureprint__procedureinitforj=i-1downto0dobegin__varifa[j]=a[i]andwritelnanslen__xlongintopt[j]+1opt[i]thenwritelnanstime__beginopt[i]=opt[j]+1closeinput__assigninput_finanslen=0closeoutput__resetinputfori=1tondoend__assignoutput_foutifopt[i]anslenthenbegin__rewriteoutputanslen=opt[i]init__n=0fillcharopt_sizeofopt_0main__repeata[0]=-maxlongintprint__incnfori=1tondoend__reada[n]forj=i-1downto0do__choruspasccpp来源:NOIP2004提高组第一题__N-K位同学出列,使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2…,K,他们的身高分别为T1,T2,…,TK,则他们的身高满足T1TiTi+1…TK1=i=K。__你的任务是,已知所有N位同学的身高,计算最少需要几位同学出列,可以使得剩下的同学排成合唱队形。__【输入文件】__输入文件chorusin的第一行是一个整数N2=N=100,表示同学的总数。第一行有n个整数,用空格分隔,第i个整数Ti130=Ti=230是第i位同学的身高厘米。__【输出文件】__输出文件chorusout包括一行,这一行只包含一个整数,就是最少需要几位同学出列。__【样例输入】__8__186186150200160130197220__【样例输出】__4__【数据规模】__对于50%的数据,保证有n=20;__对于全部的数据,保证有n=100。__【问题分析】__出列人数最少,也就是说留的人最多,也就是序列最长。__这样分析就是典型的最长下降子序列问题。只要枚举每一个人站中间时可以的到的最优解。显然它就等于,包括他在内向左求最长上升子序列,向右求最长下降子序列。__我们看一下复杂度:__计算最长下降子序列的复杂度是O(N2),一共求N次,总复杂度是O(N3)。这样的复杂度对于这个题的数据范围来说是可以AC的。但有没有更好的方法呢?__其实最长子序列只要一次就可以了。因为最长下降(上升)子序列不受中间人的影响。__只要用OPT1求一次最长上升子序列,OPT2求一次最长下降子序列。这样答案就是N-maxopt1[i]+opt2[i]-1__复杂度由O(N3)降到了O(N2)。__【源代码】varilongint__programchorusopt1_opt2_aarray[0maxn]ofbegin__constlongintassigninput_fin__fin=chorusinn_anslongintresetinput__fout=chorusoutprocedureinitassignoutput_fout__maxn=200varrewriteoutput__readlnnopt1[i]=opt1[j]+1begin__fori=1tondoa[n+1]=-maxlongintwritelnn-ans+1__reada[i]fori=ndownto1docloseinput__endforj=i+1ton+1docloseoutput__proceduremainifa[j]a[i]andend__varopt2[j]+1opt2[i]thenbegin__i_jlongintopt2[i]=opt2[j]+1init__beginans=0main__a[0]=-maxlongintfori=1tondoprint__fori=1tondoifopt1[i]+opt2[i]ansthenend__forj=i-1downto0doans=opt1[i]+opt2[i]__ifa[j]a[i]andend__opt1[j]+1opt1[i]thenprocedureprint__buylowpasccpp来源USACO4-3-1__‚逢低吸纳‛是炒股的一条成功秘诀。如果你想成为一个成功的投资者,就要遵守这条秘诀__逢低吸纳_越低越买__这句话的意思是:每次你购买股票时的股价一定要比你上次购买时的股价低按照这个规则购买股票的次数越多越好,看看你最多能按这个规则买几次。__给定连续的N天中每天的股价。你可以在任何一天购买一次股票,但是购买时的股价一定要比你上次购买时的股价低。写一个程序,求出最多能买几次股票。__以下面这个表为例_某几天的股价是__天数123456789101112__股价686954646864706778629887__这个例子中_聪明的投资者按上面的定义,如果每次买股票时的股价都比上一次买时低,那么他最多能买4次股票。一种买法如下可能有其他的买法__天数25610__股价69686462__【输入文件】buylowin__第1行N1=N=5000_表示能买股票的天数。__第2行以下N个正整数可能分多行,第i个正整数表示第i天的股价这些正整数大小不会超过longintpascallongc++__【输出文件】buylowout__只有一行,输出两个整数:__能够买进股票的天数长度达到这个值的股票购买方案数量__在计算解的数量的时候,如果两个解所组成的字符串相同,那么这样的两个解被认为是相同的(只能算做一个解)。因此,两个不同的购买方案可能产生同一个字符串,这样只能计算一次。__【输入样例】__12__6869546468647067__78629887__【输出样例】__42__【问题分析】__从题目描述就可以看出这是最长下降子序列问题,于是求解第一问不是难事,以天数为阶段,设计状态opt[i]表示前i天中要买第i天的股票所能得到的最大购买次数。__状态转移方程:__opt[i]=maxopt[j]+1a[i]=a[j]_0=ji{a[i]存第i天股价}__最大的opt[i]就是最终的解。__第二问呢,稍麻烦一点。__从问题的边界出发考虑问题,当第一问求得一个最优解opt[i]=X时,__在1到N中如果还有另外一个opt[j]=x那么选取J的这个方案肯定是成立的。__是不是统计所有的opt[j]=x的个数就是解了呢?__显然没那么简单,因为选取J这天的股票构成的方案不见得=1,看下面一个例子:__564312__方案一:5431__方案二:5432__方案三:6431__方案四:6432__x=4__也就是所虽然opt[5]=X和opt[6]=X但个数只有两个,而实际上应该有四个方案,但在仔细观察发现,构成opt[5]=x的这个方案中opt[j]=x-1的方案数有两个_opt[j]=x-2的有一个,opt[j]=x-3的有一个……__显然这是满足低归定义的设计函数F(i)表示前I张中用到第i张股票的方案数。__递推式:__1i=0__Fi=SumFj0=j=n_a[j]a[i]_opt[j]=opt[i]-1{sum代表求和}__答案=sumFj{0j=n_opt[j]=x}__复杂度:__求解第一问时间复杂度是ON2_求解第二问如果用递推或递归+记忆化时间复杂度仍为O(N2)但要是用赤裸裸的递归那就复杂多了……,因为那样造成了好多不必要的计算。__你认为这样做就解决了这道题目了么?还没有,还要注意一些东西:__(1)如果有两个方案中出现序列一样,视为一个方案,要需要加一个数组next用next[i]记录和第i个数情况一样(即:opt[i]=opt[j]且a[i]=a[j])可看做一个方案的最近的位臵。__递推时j只要走到next[i]即可。__(2)为了方便操作可以将a[n+1]赋值为-maxlongint这样可以认为第n+1个一定可以买,答案就是sumFn+1。__(3)看数据规模显然要用高精度。__注:USACO上最后一个点错了。我在程序中做了处理。__【源代码】endforj=i-1downtonext[i]doprogrambuylowprocedureHincvarifopt[j]=opt[i]-1andconstxarrtypeyarrtypea[j]a[i]then__fin=buylowinvarHincF[i]_F[j]__fout=buylowouti_zlongintend__maxn=5010beginprocedureprint__maxsize=10z=0var__jz=100000000fori=1tomaxsizedoi_top_mlongint__typebeginbegin__arrtype=array[0maxsize]ofz=zdivjz+x[i]+y[i]writeopt[n+1]-1___longintx[i]=zmodjztop=maxsize__varendwhiletop1anda_opt_nextarray[0maxn]ofendF[n+1][top]=0do__longintproceduremaindectop__Farray[0maxn]ofarrtypevarwriteF[n+1_top]__nlonginti_jlongintfori=top-1downto1doprocedureinitbeginbegin__vara[0]=maxlongintm=F[n+1_i]__ilonginta[n+1]=-maxlongintwhilemmaxsizediv10dobeginfori=1ton+1dobegin__assigninput_finforj=0toi-1dowrite0__resetinputifa[j]a[i]andm=m10__assignoutput_foutopt[j]+1opt[i]thenend__rewriteoutputopt[i]=opt[j]+1writeF[n+1_i]__readlnnfori=1tondoend__ifn=5then{最后beginwriteln__一个点错了,我只好这么写了}j=i-1closeinput__beginwhilej0andcloseoutput__writeln25opt[i]opt[j]ora[i]a[j]end__closeinputdobegin__closeoutputdecjinit__haltnext[i]=jmain__endendprint__fori=1tondoF[0_1]=1end__reada[i]fori=1ton+1do__shipspasccpp来源:《奥赛经典》(提高篇)____PALMIA国家被一条河流分成南北两岸,南北两岸上各有N个村庄。北岸的每一个村庄有一个唯一的朋友在南岸,且他们的朋友村庄彼此不同。__每一对朋友村庄想要一条船来连接他们,他们向政府提出申请以获得批准。由于河面上常常有雾,政__府决定禁止船只航线相交(如果相交,则很可能导致碰船)。__你的任务是编写一个程序,帮助政府官员决定批准哪些船只航线,使得不相交的航线数目最大。__【输入文件】shipsin__输入文件由几组数据组成。每组数据的第一行有2个整数X,Y,中间有一个空格隔开,X代表PALMIA河的长度(10=X=6000),Y代表河的宽度(10=Y=100)。第二行包含整数N,表示分别坐落在南北两岸上的村庄的数目(1=N=5000)。在接下来的N行中,每一行有两个非负整数C,D,由一个空格隔开,分别表示这一对朋友村庄沿河岸与PALMIA河最西边界的距离(C代表北岸的村庄,D代表南岸的村庄),不存在同岸又同位臵的村庄。最后一组数据的下面仅有一行,是两个0,也被一空格隔开。__【输出文件】shipsout__对输入文件的每一组数据,输出文件应在连续的行中表示出最大可能满足上述条件的航线的数目。__【输入样例】__304__7__224__26__103__1512__98__1717__42__00__【输出样例】__4__【问题分析】__这道题目相对来说思考难度较高,从字面意义上看不出问题的本质来,有点无法下手的感觉。这里我给大家推荐两种思考这类问题的方法。__法一:寻找规律法(我前面总结提到的第3个方法)__寻找规律自然要推几组数据,首先当然有从样例入手;____仔细观察上图:红色航线是合法的,那么他们满足什么规律呢?__C1C2C3C4__北岸红线的端点:491517__南岸红线的端点:281217__D1D2D3D4__不难看出无论线的斜率如何,都有这样的规律:__C1C2C3C4且D1D2D3D4__如果我们把输入数据排升序,问题变抽象为:__在一个序列(D)里找到最长的序列满足DIDJDk……且ijk__这样的话便是典型的最长非降子序列问题了。。。。__法二:边界条件法(我前面总结提到的第4个方法)__边界法其实就是把数据往小了缩,显然N=1是答案是1。N=2时呢?__考虑这样一组数据:__N=2__C1D1__C2D2__当C1C2时,如果D1D2那么一定会相交,反之则不会相交。__当C1C2时,如果D1D2那么一定会相交,反之则不会相交。__N=3__C1D1__C2D2__C3D3__……__其实不用在推导N=3了,有兴趣的可以推导去。看N=2时就能得出:__对于任意两条航线如果满足CiCj且DiDj则两条航线不相交。这样的话要想在一个序列里让所有的航线都不相交那比然满足,C1C2C3…Cans且D1D2D3…Dans,也就是将C排序后求出最长的满足这个条件的序列的长度就是解。__这样分析后显然是一个最长非降子序列问题。__复杂度:排序可以用O(nlogn)的算法,求最长非降子序列时间复杂度是On2__总复杂度为O(n2)____【源代码】i=Lforj=0toi-1do__programshipsj=rifa[j]da[i]d__constx=a[i+jdiv2]copt[j]+1opt[i]then__fin=shipsinrepeatopt[i]=opt[j]+1__fout=shipsoutwhilea[i]cxdoans=-maxlongint__maxn=5010incifori=1tondo__typewhilea[j]cxdoifansopt[i]then__retype=recorddecjans=opt[i]__C_Dlongintifi=jthenwritelnans__endbeginend__vary=a[i]begin__x_y_n_anslonginta[i]=a[j]assigninput_fin__aarray[0maxn]ofretypea[j]=yresetinput__optarray[0maxn]oflongintinciassignoutput_fout__procedureinitdecjrewriteoutput__varendreadx_y__ilongintuntilijwhilex+y0do__beginifjLthenquickL_jbegin__readlnnifirthenquicki_rinit__fori=1tondoendmain__reada[i]c_a[i]dproceduremainreadx_y__endvarend__procedurequickL_rlonginti_jlongintcloseinput__varbegincloseoutput__i_j_xlongintfillcharopt_sizeofopt_0end__yretypequick1_n__beginfori=1tondoand____12背包问题__首先说说背包问题的基本模型:__现有N个物品,每个物品的价值为V,重量为W。求用一个载重量为S的背包装这写物品,使得所装物品的总价值最高。__背包问题用贪心和搜索解,当然效果不佳,不过在我的贪心和搜索总结中会说到。显然标准的解法是动态规化,我在解决这个问题时习惯设计一维状态,还可以设计二维的,二维状态在下面会讲,现在只讨论用一维状态实现背包问题。__背包问题的分类:__1小数背包物品的重量是实数,如油,水等可以取167升……__2整数背包:101背包:每个物品只能选一次,或不选。不能只选一部分__2部分背包:所选物品可以是一部分。__3多重背包:背包不只一个。__小数背包:在贪心总结中会细讲。__整数背包:__部分背包:同小数背包。__01背包:这个问题是最经常出现的问题,应该熟练掌握。__我们先看一下01背包的简化版:__现有N个物品,每个物品重量为W,这些物品能否使在载重量为S的背包装满(即重量和正好为S)?如过不能那能使物品重量和最重达到多少?__针对这一问题我们以物品的个数分阶段,设计一个状态opt[i]表示载重量为i的背包可否装满,显然opt[i]的基类型是boolean。__决策是什么呢?__当要装第i个物品时,如果前i-1个物品可以使载重为k的背包装满,那么载重为k+w[i]的背包就可以装满。于是对于一个opt[j]来说,只要opt[j-w[i]]是true(表示可装满)那opt[j]就可以装满,但要注意:针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几次,因为k+w[i]可装满那k+w[i]+w[i]就可装满,但实际上是装不满的因为物品只有一个。解决这个问题很简单,只要逆向推导就OK了。__这样划分阶段,设计状态,满足无后效性和么?__显然对与一个每一个阶段都是独立的,物品的顺序并不影响求解,因为装物品的次序不限。而对于opt[j]只考虑opt[j-w[i]]而不考虑后面的,所以满足无后效性。__有了上面的分析不难写出状态转移方程:__opt[j]=opt[j-w[1]]{opt[j-w[i]]=true}__时间复杂度:__阶段数OS状态数(ON)转移代价(O1)=O(SN)__下面看几个例题:__packpasccpp来源:NOIP2001普及组第四题__有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30=,每个物品有一个体积(正整数)。__要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。__【输入文件】__第一行一个正整数V表示箱子的容量,第二行一个正整数N表示物品个数,接下来N行列出这N个物品各自的体积。__【输出文件】__单独一行,表示箱子最小的剩余空间。__【输入样例】__24__6__8__3__12__7__9__7__【输出样例】____【问题分析】__本题是经典的01背包问题,并且是01背包的简化版,把箱子看做背包,容量看做载重量,体积看做重量,剩余空间最小也就是尽量装满背包。于是这个问题便成了:__有一个栽重量为V的背包,有N个物品,尽量多装物品,使背包尽量的重。__设计一个状态opt[i]表示重量i可否构成。__状态转移方程:opt[j]=opt[j-w[1]]{opt[j-w[i]]=true}__最终的解就是v-x(x=n且opt[x]=true且opt[x+1n]=false)。__【源代码1】resetinputopt[j]=true__programpackassignoutput_foutx=v__constrewriteoutputwhilenotopt[x]dodecxfin=packinreadvend__fout=packoutreadnprocedureprint__maxv=20010fori=1tondobegin__maxn=100readw[i]writelnv-x__varendcloseinput__optarray[0maxv]ofproceduremaincloseoutput__booleanvarend__warray[0maxn]oflonginti_jlongintbegin__v_n_xlongintbegininit__procedureinitfillcharopt_sizeofopt_falsemain__varopt[0]=trueprint__ilongintfori=1tondoend__beginforj=vdowntow[i]do__assigninput_finifopt[j-w[i]]then__来源:NOIP1996(提高组)第四题__设有1g、2g、3g、5g、10g、20g的砝码各若干枚(其总重=1000),用他们能称出的重量的种类数。__【输入文件】__a1a2a3a4a5a6__(表示1g砝码有a1个,2g砝码有a2个,…,20g砝码有a6个,中间有空格)。__【输出文件】__Total=N__(N表示用这些砝码能称出的不同重量的个数,但不包括一个砝码也不用的情况)。__【输入样例】__110000__【输出样例】__TOTAL=3__【问题分析】__把问题稍做一个改动,已知a1+a2+a3+a4+a5+a6个砝码的重量w[i]_w[i]∈{1_2_3_5_10_20}其中砝码重量可以相等,求用这些砝码可称出的不同重量的个数。__这样一改就是经典的01背包问题的简化版了,求解方法完全和上面说的一样,这里就不多说了,只是要注意这个题目不是求最大载重量,是统计所有的可称出的重量的个数。__【源代码1】reada[i]var__programP4endans_ilongint__constproceduremainbegin__maxn=1010varans=0__warray[16]ofi_j_klongintfori=1tomaxndo__longint=1_2_3_5_10_20beginifopt[i]then__varfillcharopt_sizeofopt_falseincans__optarray[0maxn]ofopt[0]=truewritelnans__booleanfori=1to6doend__aarray[16]oflongintforj=1toa[i]dobegin__procedureinitfork=maxndowntow[i]doinit__varifopt[k-w[i]]main__ilongintthenopt[k]=trueprint__beginendend__fori=1to6doprocedureprint__来源:vijosP1059__XC的儿子小XC最喜欢玩的游戏用积木垒漂亮的城堡。城堡是用一些立方体的积木垒成的,城堡的每一层是一块积木。小XC是一个比他爸爸XC还聪明的孩子,他发现垒城堡的时候,如果下面的积木比上面的积木大,那么城堡便不容易倒。所以他在垒城堡的时候总是遵循这样的规则。__小XC想把自己垒的城堡送给幼儿园里漂亮的女孩子们,这样可以增加他的好感度。为了公平起见,他决定把送给每个女孩子一样高的城堡,这样可以避免女孩子们为了获得更漂亮的城堡而引起争执。可是他发现自己在垒城堡的时候并没有预先考虑到这一点。所以他现在要改造城堡。由于他没有多余的积木了,他灵机一动,想出了一个巧妙的改造方案。他决定从每一个城堡中挪去一些积木,使得最终每座城堡都一样高。为了使他的城堡更雄伟,他觉得应该使最后的城堡都尽可能的高。__任务:__请你帮助小XC编一个程序,根据他垒的所有城堡的信息,决定应该移去哪些积木才能获得最佳的效果。__【输入文件】__第一行是一个整数NN=100,表示一共有几座城堡。以下N行每行是一系列非负整数,用一个空格分隔,按从下往上的顺序依次给出一座城堡中所有积木的棱长。用-1结束。一座城堡中的积木不超过100块,每块积木的棱长不超过100。__【输出文件】__一个整数,表示最后城堡的最大可能的高度。如果找不到合适的方案,则输出0。__【输入样例】__2__21–1__321-1__【输出样例】3__【提交链接】__vijos__【问题分析】__首先要说明一点,可以挪走任意一个积木,不见得是最上面的。__初看题目有点茫然,但抽象一下就。。。。。。。。。。__其实塔好积木在拿走就相当于当初搭的时候没选拿走的积木。这样一转化思维问题就清楚了。把积木可搭建的最大高度看做背包的载重,每块积木的高度就是物品的重量。也就是用给定的物品装指定的包,使每个包装的物品一样多,且在符合条件的前提下尽量多。__这样就变成经典的背包问题了。__对于每一个城堡求一次,最终找到每一个城堡都可达到的最大高度即可。__【源代码1】ilongintreadm__constbeginend__maxhig=7000can=truefori=1totopdo__maxn=100fori=1tondoforj=tothigdownto1dovarifnotopt[i_m]thenifj-a[i]=0andn_toplongintexitfalseopt[ii_j-a[i]]then__optarray[0maxn_0maxhig]endopt[ii_j]=true__ofbooleanproceduremainend__aarray[0maxn]oflongintvarans=maxhig__procedureinitii_m_tothig_i_j_anslongintwhilenotopt[1_ans]dovarbegindecans__ilongintforii=1tondowhilenotcanansdo__beginbegindecans__readlnntop=0writelnans__fillcharopt_sizeofopt_falsereadmend__fori=1tondotothig=0begin__opt[i_0]=truewhilem0doinit__endbeginmain__functioninctopend__canmlongintbooleana[top]=m__varinctothig_m__回顾上面的内容充分说明动态规划的本质就是递推。其实按照我的理解(动规涉及最优决策,递推是单纯的总结)背包问题的简化版更准确点算是递推而非动态规划,至于动归和递推之间的界线本来就很模糊(至少我这么认为)把它看做什么都可以,没必要咬文嚼字。__回到01背包的原问题上(如果你忘了就去上面看看)。__如果在不知道这个模型的情况下我们怎么做这个题呢?__这就要用到第一节提到的方法二:三要素法。__题目中明确说明对于一个物品要不就拿走要不就放下,其实题目赤裸裸的告诉我们决策就是不拿(用0表示)或拿(用1表示)。这样想都不用想就知道了决策,这也是本题的突破口。知道了决策写个搜索的程序应该是很轻松的了。__那么阶段是什么呢?__显然,给你一堆东西让你往包里塞,你当然是一个一个的那来,塞进去。那么阶段很明显就是物品的个数。__状态又是什么呢?__有的人在装东西是有个习惯(比如说我)就是先把东西分类,然后把同类的东西打个小包,最后在把小包放进去,我们可以按这个思想给物品打一些小包,也就是按照单位为1的递增的顺序准备好多小包,比如载重是6的包,可以为它准备载重是1,2,3,4,5的小包。这样状态就可以想出来了:__设计状态opt[i,j]表示装第i个物品时载重为j的包可以装到的最大价值。__opt[i-1_j]j-w[i]0,i0__状态转移方程:opt[i_j]=__max{opt[i-1_j]_opt[i-1_j-w[i]]+v[i]}j-w[i]=0_i0__w[i]第i个物品的重量,v[i]第i个物品的价值__解释:要载重为j的背包空出w[i](j-w[i])的空间且装上第i个物品,比不装获得的价值大就装上它。边界条件:opt[0_i]=0i∈{1S}__注:__这种二维的状态表示应该在下节讲,但是为了方便理解先在这里说了。__上面的方法动态规划三要素都很明显,实现也很简单。但是在我初学背包时却用另外一种一维的状态表示法。__用第一节说的思考方法五(放宽约束和增加约束)在重新思考一下这个问题:__怎么放宽约束呢?__把题目中的价值去掉,不考虑价值即最优就变成背包问题的简化版了。那简化版的求解对我们有何启示呢?__再一次增加约束:背包只能装满。__显然对于N个装满背包的方案中只要找到一个价值最大的就是问题的解。那么装不满怎么办呢?其实装不满背包,它总要达到一定的重量(X)。我们可以把这种情况看作是装满一个载重为X的小包。__

文档信息:

  • 大小:382KB
  • 页数:45页
  • 格式:doc格式

点击图片查看更多:

隐藏内容: ********, 支付¥5.00下载

发表评论

您必须才能发表评论!