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

动态规划与回溯方法


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 部分,这样就得到了一个解。若尝试到某一步时发现已经无法继续, 就返回到前一步,修改已经求出的上一部分,然后再继续向后求解。这样,直到回溯到第一步,并且 已经将第一步的所有可能情况都尝试过之后,即可得出问题的全部解。


相关文章:
算法分析与程序设计动态规划及回溯法解01背包问题.doc
算法分析与程序设计动态规划回溯法解01背包问题 - 动态规划法、回溯法解 0-1 背包问题 2012 级 计科 庞佳奇 一、 1. 问题描述与分析 动态规划算法通常用于...
算法分析复习题目及答案.doc
算法分析复习题目及答案 - 一、选择题 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法...
算法设计与分析复习题目及答案.doc
六、算法设计题(本题 15 分) 分别用贪心算法、动态规划法、回溯法设计 0-1
动态规划法,回溯法,分支限界法求解TSP问题实验报告.doc
动态规划法,回溯法,分支限界法求解TSP问题实验报告_计算机软件及应用_IT/计
动态规划、回溯与分支定界_图文.ppt
动态规划回溯与分支定界 - 山东大学软件学院 数据结构、算法与应用课程 教学专
动态规划练习题(含答案).pdf
动态规划练习题(含答案) - 动态规划练习题 USACO 2.2 Subset
《算法分析与设计》期末考试复习题纲(完整版)_图文.doc
A.备忘录法 B.动态规划法 C.贪心法 D.回溯法 11. 下列算法中不能解决 0/1 背包问题的是( A )。 A.贪心法 B.动态规划 C.回溯法 D.分支限界法 12....
动态规划+回溯 练习题参考.txt
动态规划+回溯 练习题参考 - 一、动态规划练习题(vc6.0) 1.解:设第n
动态规划练习题(含答案).doc
问题描述及实现:背包问题:解决背包问题的方法有多种,动态规划,贪心算法,回溯法,分支定界法都 能解决背包问题。其中动态规划,回溯法,分支定界法都是解决 0-1 ...
算法分析复习题目及答案.doc
)。 16.最长公共子序列算法利用的算法是( A、分支界限法 B、动态规划法 17.实现棋盘覆盖算法利用的算法是( A、分治法 B、动态规划法 D、回溯法 18.下面是...
1、算法分析复习题目及答案.doc
D、回溯法 C、最大效益优先 12.下列算法中通常以深度优先方式系统搜索问题解的是( A、备忘录法 B、动态规划法 C、贪心法 B ) 13.备忘录方法是那种算法的...
算法分析复习题(含答案).doc
(A)分治策略 (B)动态规划法 (C)贪心法 (D)回溯法 4、使用分治法求解
算法分析与设计之动态规划法_图文.ppt
算法分析与设计之动态规划法 - 第六章 1 2 3 4 5 动态规划法 概述 图问题中的动态规划法 组合问题中的动态规划法 查找问题中的动态规划法 小结 海盗分钻石...
算法期末复习题.doc
算法期末复习题 - 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义最优解 B、动态规划法 2、下列不是动态...
动态规划:从新手到专家.doc
动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题 的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间 复杂度,因此它比回溯法...
用动态规划法与回溯法实现0-1背包问题的比较_论文.pdf
动态规划与回溯法实现0-1背包问题的比较 - 0-1背包问题是运筹学中的著名问题。也是计算机算法中的一个经典问题。本文采用动态规划和回溯法对该问题进行求解...
算法设计与分析--回溯法.doc
0/1 背包问题是一个经典的问题,我们可以采用多种算法去求解 0/1 背包问题,比 如动态规划法、分支限界法、贪心算法、回溯法。在这里我们采用回溯法解决这个问题...
0-1背包(动态规划、回溯)和背包(贪心)实验报告.doc
三.测试数据及运行结果 1.正常测试数据(3 组)及运行结果 0-1 背包问题:动态规划法: 回溯法: 背包问题: 贪心算法: 四.调试情况,设计技巧及体会 调试情况, ...
程序设计方法动态规划法.ppt
? 可以用递归回溯方法解决 ? 建议自写递归回溯的代码 换一种思路 A:1 第2...? ? ? 阶段 状态 决策 状态转移方程 动态规划的几个概念: 阶段:据空间顺序...
第6章 动态规划法_图文.ppt
第六章 1 2 3 4 5 动态规划法 概述图问题中的动态规划法 组合问题中的...(0→1) 所以,从顶点0出发的TSP问题的最短路径长度为10,再将状态进行回溯,得...
更多相关标签: