动态规划方法例题.

动态规划方法例题最长上升子序列问题•一个序列有N个数：A[1],A[2],…,A[N]，求出最长上升子序列的长度（LIS：longestincreasingsubsequence)。•例如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,5,9),(3,4,8)等等。这些子序列中最长的长度是4，比如子序列(1,3,5,9)，(1,3,5,8)和(1,3,4,8).分析•假如我们考虑求A[1],A[2],…,A[i]的最长上升子序列的长度，其中iN，那么上面的问题变成了原问题的一个子问题(问题规模变小了，可让i=1,2,3等来分析)•然后我们定义d(i)，表示前i个数中以A[i]结尾的最长上升子序列的长度。这个d(i)就是我们要找的状态。•如果我们把d(1)到d(N)都计算出来，那么最终我们要找的答案就是这里面最大的那个。状态找到了，下一步来找状态转移方程。找出状态转移方程我们来看下面这6个数的序列：5，3，4，8，6，7我们可以得到：（下文的最长上升子序列都用LIS表示）前1个数的LIS长度d(1)=1(序列：5)•前2个数的LIS长度d(2)=1(序列：3；3前面没有比3小的)•前3个数的LIS长度d(3)=2(序列：3，4；4前面有个比它小的3)第1阶段决策选优：求最长上升子序列的长度•需要判断当前的数是否与其左边最长上升子序列构成一个上升序列，如果是，则：•d(3)=max{d(1),d(2)}+1；即第3个数左边最长上升子序列最大长度+1•前4个数的LIS长度d(4)=3(序列：3，4，8；8前面比它小的有3个数，所以d(4)=max{d(1),d(2),d(3)}+1=3状态转移方程如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：d(i)=max{d(j)}+1（1）其中j=1,2,...,i-1,A[j]A[i]有可能i前面的各个子序列中最后一个数都大于A[i]，那么d(i)=1（2）即它自身成为一个长度为1的子序列。求解LIS的C++代码段intlen=1;for(inti=0;in;++i){d[i]=1;//数组d用来保存子序列的长度for(intj=0;ji;++j)if(A[j]=A[i]&&d[j]+1d[i])d[i]=d[j]+1;if(d[i]len)len=d[i];}序列变化•求最长非降子序列(longestnon-decreasingsubsequence)，与此问题近似。只需要将上述条件A[j]A[i]改为：A[j]≤A[i]。•求最长下降子序列(longestdecreasingsubsequence)，将上述条件A[j]A[i]改为：A[j]A[i]。•如果要求最长非递增子序列（longestnon-increasingsubsequence），将上述条件A[j]A[i]改为：A[j]≥A[i]。•蓝桥杯网站练习系统算法训练中的“拦截导弹”问题，本质上就是一个求最长非递增子序列长度的题。例1拦截导弹•某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。•（蓝桥网编号：ALGO-13VIP试题）拦截导弹输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。输入第一行输入测试数据组数N（1=N=10）接下来一行输入这组测试数据共有多少个导弹m（1=m=20）接下来行输入导弹依次飞来的高度，所有高度值均是大于10的正整数。输出输出最多能拦截的导弹数目拦截导弹样例输入输出样例输入SAMPLEINPUT:28389207155300299170158653883465SAMPLEOUTPUT:638930029917015865分析•因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；所以，被拦截的导弹应该按飞来的导弹高度组成一个非递增序列。•题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要在导弹依次飞来的高度序列中寻找一个最长非递增子序列的长度。状态转移方程如果我们已经求出了d(1)到d(i-1)，那么d(i)可以用下面的状态转移方程得到：d(i)=max{d(j)}+1（1）其中j=1,2,...,i-1,A[j]≥A[i]有可能i前面的各个子序列中最后一个数都小于A[i]，那么d(i)=1（2）即它自身成为一个长度为1的子序列。只需修改这个符号，就可以求最长非递增子序列求解拦截导弹问题的C++代码段intlen=1;for(inti=0;in;++i){d[i]=1;//数组d用来保存子序列的长度for(intj=0;ji;++j)if(A[j]=A[i]&&d[j]+1d[i])d[i]=d[j]+1;if(d[i]len)len=d[i];}例2乘积最大问题描述设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。例子：有一个数字串:312，当N=3，K=1时会有以下两种分法：1）3*12=362）31*2=62这时，符合题目要求的结果是：31*2=62现在，请你设计一个程序，求得正确的答案。（蓝桥网站题目编号：ALGO-17VIP试题2013-11-07）输入输出样例输入：输入中有若干组测试数据，每组测试数据有两行：第一行共有2个自然数T，K（6=T=40，1=K=6），第二行是一个长度为T的数字串。输出:结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。输入样例:421231输出样例：62分析：划分阶段假设在n0n1…ni(2≤i≤n)中插入k个’*’。其中n0n1…nt中插入了k-1个’*’，即乘式中的第k+1项为nt+1…ni(k≤t≤i-1)，即有形式：itktnnnn1'*'10*个插入状态转移方程设F[i][k]是长度为i+1的数串中插入k个“*”的最大乘积（整型数组），0≤k≤i。ittnnnn10...]}][1[*]1][[{max]][[10itnumktFkiFtkittnnnn10...显然F[i][0]=，i=0，1，2，…，N-1；状态转移方程为高精度运算由于自然数位数的上限为40，乘号数的上限为6，因此最大乘积位数的上限接近42位。显然，运算任何整数类型都无法容纳如此之大的数据，需要采用高精度运算，这里仅介绍解题思路。为了便于大家理解算法思想，程序中只是用了在长整型范围内的数据处理，如整数的分划、合成和乘法运算等。01背包问题•一个旅行者有一个最多能用M公斤的背包，现在有N件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为P1,P2,...,Pn.若每种物品只有一件，求旅行者能获得最大总价值。输入输出•输入格式：M,NW1,P1W2,P2......输出格式：X分析•阶段：在前i件物品中，选取若干件物品放入背包中；•状态：在前i件物品中，选取若干件物品放入所剩空间为c的背包中的所能获得的最大价值；•决策：第i件物品放或者不放；状态转移方程•可以按每个物品划分阶段；•每种物品有选和不选两种选择（决策）•设F(i,j)表示前i件物品载重为j的最大效益，则有•1=i=N,0=j=M•初值：F(0,j)=0•F(N,M)即答案•显然时间复杂度为O(NM)种物品不装入第入种物品装第ijiFiiPiwjiFMaxjiF),,1(],[])[,1(),(f(i,j)=max{f(i-1,j),f(i-1,j-w[i])+P(i)}•c[i][j]数组保存了1,2,3号物品依次选择后的最大价值f(i,j)测试数据：10,3（容量为10，3个物品）3,44,55,6f(2,7)=max{f(1,7),f(1,7-4)+5)}=max{5,4+5}=9装入2号物品f(3,7)=max{f(2,7),f(2,7-5)+6)}=max{9,0+6}=9不装入3号物品主程序fori:=1tomdof[0,i]:=0;//初始化fori:=1tondof[i,0]:=0;fori:=1tondo//动态规划，递推求fforj:=1tomdobeginifj=w[i]then//背包容量够大f[i,j]:=max(f[i-1,j-w[i]]+p[i],f[i-1,j])else//背包容量不足f[i,j]:=f[i-1,j];end;例3入学考试•辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”如果你是辰辰，你能完成这个任务吗？••蓝桥网编号：ALGO-30VIP试题2013-11-08输入输出格式输入格式第一行有两个整数T（1=T=1000）和M（1=M=100），用一个空格隔开，T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的整数，分别表示采摘某株草药的时间和这株草药的价值。输出格式包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。输入输出样例样例输入7037110069112样例输出3数据规模和约定对于30%的数据，M=10；对于全部的数据，M=100。分析•这是一个典型的01背包问题•可以将T（总共能够用来采药的时间）看作背包容量•将采每一株草药需要时间的时间看作物品重量•将每株草药的价值看作物品的价值例4开心的金明•金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间他自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过N元钱就行”。今天一早金明就开始做预算，但是他想买的东西太多了，肯定会超过妈妈限定的N元。于是，他把每件物品规定了一个重要度，分为5等：用整数1~5表示，第5等最重要。他还从因特网上查到了每件物品的价格（都是整数元）。他希望在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。设第j件物品的价格为v[j]，重要度为w[j]，共选中了k件物品，编号依次为j1...jk，则所求的总和为：v[j1]*w[j1]+..+v[jk]*w[jk]请你帮助金明设计一个满足要求的购物单。•蓝桥网题目编号：ALGO-31VIP试题2013-11-08输入输出【输入文件】输入的第1行，为两个正整数，用一个空格隔开：Nm（其中N（30000）表示总钱数，m(25)为希望购买物品的个数。）从第2行到第m+1行，第j行给出了编号为j-1的物品的基本数据，每行有2个非负整数vp（其中v表示该物品的价格（v≤10000），p表示该物品的重要度（1~5））【输出文件】输出只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（100000000）。输入输出样例【输入样例】1000580024005300540032002【输出样例】3900分析这是一个有微小变化的01背包问题总钱数N可看做背包的容量，物品的价格可看作物品的重量。优化目标：在不超过N元（可以等于N元）的前提下，使每件物品的价格与重要度的乘积的总和最大。状态转移方程如下：f[i,j]=max{f[i-1,j