当前位置:首页 >> 计算机软件及应用 >>

动态规划与回溯方法



Problem Description Given a sequence a[1],a[2],a[3]......a[n], your job is to calculate the max sum of a sub-sequence. For example, given (6,-1,5,4,-7), the max sum in this sequence is 6 + (-1) + 5 + 4 = 14. Input The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000). Output For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases. Sample Input

2 5 6 -1 5 4 -7 7 0 6 -1 1 -6 7 -5
Sample Output

Case 1: 14 1 4 Case 2: 7 1 6 ////////////////////////////////////////////////////////// 求最大和子串,用动态规划的方法来做。令 f[n]为到第 n 个位置时的最大和。 则 f[n]=max{f[n-1]+data[n],data[n]} 即如果 f[n-1]+data[n]>data[n],则 f[n]=f[n-1]+data.也就是 f[n-1]>0。如果 f[n-1]>0,则后一项加上 f[n-1]肯定更大。所以本题主要求 f[1..n]。然后求出 f 中最大的一个(max(f[1..n]))。这题又要求最大串的开始与结束位置,当 f[n-1]<0 时,开始位置要重新开始记录。主要思想是这样,编写的时候可以换 一种实现形式。如下

#include<stdio.h> int main() { int s,e,max,sum,n,t,dat,i,s1,j; for (;scanf("%d",&t)!=EOF;) { 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); } } return 0; } 包括串全部为负数的情况。

回溯

1 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往 前走,能进则进,不能进则退回来,换一条路再试。 用回溯算法解决问题的一般步骤为: 一、定义一个解空间,它包含问题的解。 二、利用适于搜索的方法组织解空间。 三、利用深度优先法搜索解空间。 四、利用限界函数避免移动到不可能产生解的子空间。 问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。 回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中, 按照深度优先的策略,从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时,总是先判断 该结点是否肯定不包含问题的解。如果肯定不包含,则跳过对以该结点为根的子树的系统搜索,逐层 向其祖先结点回溯。否则,进入该子树,继续按深度优先的策略进行搜索。回溯法在用来求问题的所 有解时, 要回溯到根, 且根结点的所有子树都已被搜索遍才结束。 而回溯法在用来求问题的任一解时, 只要搜索到问题的一个解就可以结束。 这种以深度优先的方式系统地搜索问题的解的算法称为回溯法,

它适用于解一些组合数较大的问题. 递归回溯:由于回溯法是对解空间的深度优先搜索,因此在一般情况下可用递归函数来实现回溯 法如下: procedure try(i:integer); var begin if i>n then 输出结果 else for j:=下界 to 上界 do begin x:=h[j]; if 可行{满足限界函数和约束条件} then begin 置值;try(i+1); end; end; end; 说明: i 是递归深度; n 是深度控制,即解空间树的的高度; 可行性判断有两方面的内容: 不满约束条件则剪去相应子树; 若限界函数越界, 也剪去相应子树; 两者均满足则进入下一层; 搜索:全面访问所有可能的情况,分为两种:不考虑给定问题的特有性质,按事先顶好的顺序, 依次运用规则,即盲目搜索的方法;另一种则考虑问题给定的特有性质,选用合适的规则,提高搜索 的效率, 即启发式的搜索。 回溯即是较简单、较常用的搜索策略。 基本思路:若已有满足约束条件的部分解,不妨设为(x1,x2,x3,……xi),I<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;look back upon;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"。

这样,直到第一位已经取过了所有可能的值,并且将每种情况下的第二位和第三位都按上述思路取过 一遍,此时就已经得到了该问题的全部解。 由以上过程可以看出,回溯法的思路是:问题的每个解都包含 N 部分,先给出第一部分,再给 出第二部分,……直到给出第 N 部分,这样就得到了一个解。若尝试到某一步时发现已经无法继续, 就返回到前一步,修改已经求出的上一部分,然后再继续向后求解。这样,直到回溯到第一步,并且 已经将第一步的所有可能情况都尝试过之后,即可得出问题的全部解。


赞助商链接
相关文章:
算法分析复习题(含答案)
(A)分支界限算法 (B)动态规划算法 (C)贪心算法 (D)回溯算法 11、实现大整数的乘法是利用的算法( C )。(A)贪心法 (B)动态规划法 (C)分治策略 (D)回溯...
《算法分析与设计》期末考试复习题纲(完整版)
A.备忘录法 B.动态规划法 C.贪心法 D.回溯法 11. 下列算法中不能解决 0/1 背包问题的是( A )。 A.贪心法 B.动态规划 C.回溯法 D.分支限界法 12....
信息利用最大化在优化回溯法、动态规划和数值计算中的...
信息利用最大化在优化回溯法动态规划和数值计算中的应用探讨_天文/地理_自然科学_专业资料。【摘要】在算法设计中,人们往往不自觉地进行了大量多余 的运算,这些...
算法分析复习题目及答案[1]
D、回溯法 C、最大效益优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( A、备忘录法 B、动态规划法 C、贪心法 B ) 13.备忘录方法是那种算法的...
算法分析与设计复习题及参考答案
3.简述动态规划算法求解的基本要素。 4.简述回溯法的基本思想。 5.简要分析在递归算法中消除递归调用,将递归算法转化为非递归算法的方法。 6.简要分析分支限界法...
算法分析复习题目及答案16-12-10
算法分析复习题目及答案16-12-10 - 一。选择题 1、二分搜索算法是利用( A、分治策略 B、动态规划法 A )实现的算法。 C、贪心法 D D、回溯法 )。 D、...
...A.回溯方法 B.分治法 C.动态规_答案_百度高考
以下的算法设计方法中,()以获取问题最优解为目标。 A.回溯方法 B.分治法 C.动态规划 D.递推正确答案及相关解析 正确答案 C 解析 本题考查算法基础知识。...
算法分析与程序设计动态规划及回溯法解01背包问题
算法分析与程序设计动态规划回溯法解01背包问题_计算机软件及应用_IT/计算机_专业资料。今日推荐 88份文档 2014全国高考状元联手分享状元笔记 ...
1、算法分析复习题目及答案
D、回溯法 C、最大效益优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( A、备忘录法 B、动态规划法 C、贪心法 B ) 13.备忘录方法是那种算法的...
算法分析复习题目及答案
矩阵连乘问题的算法可由( A、分支界限算法 B、动态规划算法 D、最优子结构性质 B)设计实现。 C、贪心算法 D、回溯算法 A D、数组 )。 26. 分支限界法解...
更多相关标签: