动态规划与回溯方法

ProblemDescriptionGivenasequencea[1],a[2],a[3] a[n],yourjobistocalculatethemaxsumofasub-sequence.Forexample,given(6,-1,5,4,-7),themaxsuminthissequenceis6+(-1)+5+4=14.InputThefirstlineoftheinputcontainsanintegerT(1<=T<=20)whichmeansthenumberoftestcases.ThenTlinesfolloweachlinestartswithanumberN(1<=N<=100000),thenNintegersfollowed(alltheintegersarebetween-1000and1000).OutputForeachtestcase,youshouldoutputtwolines.Thefirstlineis"Case##meansthenumberofthetestcase.Thesecondlinecontainsthreeintegers,theMaxSuminthesequence,thestartpositionofthesub-sequence,theendpositionofthesub-sequence.Iftherearemorethanoneresult,outputthefirstone.Outputablanklinebetweentwocases.SampleInput256-154-7706-11-67-5SampleOutputCase1:1414Case2:716//////////////////////////////////////////////////////////求最大和子串，用动态规划的方法来做。令f[n]为到第n个位置时的最大和。则f[n]二max{f[n-1]+data[n],data[n]}即如果f[nT]+data[n]>data[n],则f[n]二f[nT]+data.也就是f[nT]>0。如果f[n-1]>0，则后一项加上f[n-1]肯定更大。所以本题主要求f[1..n]。然后求出f中最大的一个(max(f[1..n]))。这题又要求最大串的开始与结束位置，当f[n-1]<0时，开始位置要重新开始记录。主要思想是这样，编写的时候可以换一种实现形式。如下#include<stdio.h>intmain(){ints,e,max,sum,n,t,dat,i,sl,j;for(;scanf("%d",&t)!=E0F;){j=1;while(t—){max=—10000;sum=0;scanf("%d"，&n);s1=1;for(i=1;i<=n;i++){scanf("%d",&dat);sum+=dat;if(sum>max){max=sum;s=s1;e=i;}if(sum<0){sum=0;s1=i+1;}}if(j—1!=0)printf("\n");printf("Case%d:\n",j++);printf("%d%d%d\n",max,s,e);}}return0;}包括串全部为负数的情况。

回溯回溯1回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：一、 定义一个解空间，它包含问题的解。二、 利用适于搜索的方法组织解空间。三、 利用深度优先法搜索解空间。四、 利用限界函数避免移动到不可能产生解的子空间。问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,它适用于解一些组合数较大的问题•递归回溯：由于回溯法是对解空间的深度优先搜索，因此在一般情况下可用递归函数来实现回溯法如下：proceduretry(i:integer);varbeginifi>nthen输出结果elseforj:=下界to上界dobeginx:=h[j];if可行｛满足限界函数和约束条件｝thenbegin置值；try(i+1);end;end;end;说明：i是递归深度；n是深度控制，即解空间树的的高度；可行性判断有两方面的内容：不满约束条件则剪去相应子树；若限界函数越界，也剪去相应子树；两者均满足则进入下一层；搜索：全面访问所有可能的情况，分为两种：不考虑给定问题的特有性质，按事先顶好的顺序，依次运用规则，即盲目搜索的方法；另一种则考虑问题给定的特有性质，选用合适的规则，提高搜索的效率，即启发式的搜索。回溯即是较简单、较常用的搜索策略。基本思路：若已有满足约束条件的部分解，不妨设为(x1,x2,x3,……xi),l<n,则添加x(i+1)属于s(i+2)，检查(x1,x2,……,xi,x(i+1))是否满足条件，满足了就继续添加x(i+2)、s(i+2)，若所有的x(i+1)属于s(i+1)都不能得到部分解，就去掉xi，回溯到(xi,x2,……x(i-1))，添加那些未考察过的x1属于s1，看其是否满足约束条件，为此反复进行，直至得到解或证明无解。2回溯[recall;lookbackupon;trace]上溯，向上推导这种鱼有回溯的习惯回溯的设计1•用栈保存好前进中的某些状态.2.制定好约束条件【例1】从1到X这X个数字中选出N个,排成一列，相邻两数不能相同，求所有可能的排法。每个数可以选用零次、一次或多次。例如，当N=3、X=3时，排法有12种：121、123、131、132、212、213、231、232、312、313、321、323。【分析】以N=3,X=3为例，这个问题的每个解可分为三个部分：第一位，第二位，第三位。先写第一位，第一位可选1、2或3,根据从小到大的顺序，我们选1；那么，为了保证相邻两数不同，第二位就只能选2或3了，我们选2；最后，第三位可以选1或3,我们选1；这样就得到了第一个解"121"。然后，将第三位变为3,就得到了第二个解"123"。此时，第三位已经不能再取其他值了，于是返回第二位，看第二位还能变为什么值。第二位可以变为3,于是可以在"13"的基础上再给第三位赋予不同的值1和2,得到第三个解"131"和"132"。此时第二位也已经不能再取其他值了，于是返回第一位，将它变为下一个可取的值2,然后按顺序变换第二位和第三位，得到"212"、"213"、"231""232"。这样，直到第一位已经取过了所有可能的值，并且将每种情况下的第二位和第三位都按上述思路取过一遍，此时就已经得到了