深搜与简单的动态规划.ppt

第9讲深搜与简单的动态规划 深度优先搜索算法的框架 proceduredfs i 搜索第i个分量Xibeginifi n 1找到一个解 ifi n 1thenexit 防止数组越界 合适的剪枝优化 最优化剪枝与可行性剪枝forXi Si且使得 X1 X2 Xi 1 Xi 满足约束条件dobegin记录满足条件的Xi 添加相应的标志 dfs i 1 删除标志 恢复之前的状态 根据具体情况选择 回溯endend 1 数字三角形有一个数字三角形 编程求从最顶层到最底层的一条路所经过位置上数字之和的最大值 每一步只能向左下或右下方向走 下图数据的路应为7 3 8 7 5 和为30 输入 第一行 R 1 R 100 数字三角形共有R行 以下R行 依次表示数字三角形中每行中的数字 每个数都是非负的 且 100 输出 一个正整数 路径上数字之和的最大值 输入样例 5738810274445265输出样例 30 738810274445265 算法1 深度优先搜索算法DFS 二维数组a i j 存储数字三角形 Proceduredfs sum i j integer 从a 1 1 到走到第i行第j列即a i j 时所取得的值为sumbeginifi nthenbeginifsum maxthenmax sum exit end dfs sum a i 1 j i 1 j 向左下方走dfs sum a i 1 j 1 i 1 j 1 向右下方走end 开始时 dfs a 1 1 1 1 结果 max 738810274445265 738810274445265 为什么当n较大时速度慢 f array 0 100 0 100 ofinteger f i j i j 到最后一行经过数的和的最大值 f i j max f i 1 j f i 1 j 1 a i j 初始 f n i a n i 目标 f 1 1 算法2 functionmax a b longint longint beginifa bthenexit a elseexit b end Proceduredfs i j integer 求 i j 到最后一行的最大和beginifi nthenbeginf i j a i j exit end iff i j 0thenexit dfs i 1 j dfs i 1 j 1 f i j max f i 1 j f i 1 j 1 a i j end Begininit fillchar f sizeof f 0 dfs 1 1 writeln f 1 1 End 设f i j a i j 到达第n行a n k k 1 n 的最大值 递推关系 f i j max f i 1 j f i 1 j 1 a i j 初始 f n i a n i 1 i n目标 f 1 1 算法3 738810274445265 proceduremain beginfori 1tondof n i a n i fori n 1downto1do 枚举行 forj 1toido 枚举每行的元素 f i j max f i 1 j f i 1 j 1 a I j 枚举走法 writeln f 1 1 end functionmax a b integer integer beginmax a ifb maxthenmax b end 依次求从起点 1 1 到点 i j 的最大值 正向设f i j 为从a 1 1 到达a i j 时取得的最大值 根据题意可得出递推关系 f i j max f i 1 j 1 f i 1 j a i j 初始 f 1 1 a 1 1 目标 max f n i 1 i n 738810274445265 算法4 proceduremain 顺推 beginf 1 1 a 1 1 fori 2tondoforj 1toidof i j max f i 1 j 1 f i 1 j a i j ans f n 1 fori 2tondoiff n i ansthenans f n i writeln ans end 总结 算法1 一般的搜索 效率很低 算法2 记忆化搜索 效率高 算法3和算法4 动态规划算法 效率高 在一个n m的棋盘内 一些格子里有垃圾要拾捡 现在有一个能捡垃圾的机器人从左上格子里出发 每次只能向右或者向下走 每次他到达一个点 就会自动把这个点内的垃圾拾掉 问 机器人到达右下角时最多能拾多少垃圾 数据范围 n 100 m 100 2 Robots机器人捡垃圾 样例输入 67712142426444766 样例输出 5 算法1 dfs C i j 1表示 i j 点有垃圾 C i j 0表示没有 proceduredfs i j sum longint 从 i j 走到终点 n m 能捡到的垃圾数是sumbeginif i n and j m thenifsum ansthenans sum ifi nthendfs i 1 j sum c i 1 j ifj mthendfs i j 1 sum c i j 1 end 初始 dfs 1 1 c i j 结果是 ans 算法2 因为只能向右或者向下走 也就是说不能走回头路 设f i j 表示从 1 1 点开始走到 i j 的时候 最多捡了多少垃圾 根据 i j 只能从 i 1 j 或者 i j 1 走过来 得出递推关系 f i j Max f i 1 j f i j 1 c i j 初始 f 0 i 0 0 i m f j 0 0 0 j n 目标 f n m 简单的主程序 Fillchar f sizeof f 0 fori 1tondoforj 1tomdof i j max f i j 1 f i 1 j c i j Writeln f n m 3 简单的背包问题 0 1背包 设有 种物品 每种物品有一个重量及一个价值 同时有一个背包 最大载重量为M 今从 种物品中选取若干件 使其重量的和小于等于m 而价值的和为最大 N 100 M 1000 输入数据 第一行两个数 物品总数 背包载重量M 两个数用空格分隔 第二行N个数 为 种物品重量Wi 1000 两个数用空格分隔 第三行N个数 为N种物品价值Vi 1000 两个数用空格分隔 输出数据 总价值 输入样例1 41043571572025输出样例1 35 输入样例2 420291015291016输出样例2 19 Dfs算法 constmaxn 100 varn m integer n 物品数量 m 背包容量w array 1 maxn ofinteger 物品重量v array 1 maxn ofinteger 物品价值best longint 最大价值 proceduredfs i left value longint i 搜索第i件物品 判断放还是不放到背包里 left 背包的剩余空间 value 已装物品的价值beginifi n 1thenifvalue bestthenbest value ifi nthenexit 防止溢出dfs i 1 left value 不装iifleft w i then 装idfs i 1 left w i value v i end 主程序 init dfs 1 m 0 writeln best 背包的容量0 10 物品0 4 4件物品背包容量 10 算法2 设f i j 从1到i件物品中选若取干件放到容量为j的背包中 获得的最大价值 目标是 f n m 用f i j 表示在第 到第i件物品中装入重量为j的背包获得的最大价值 f i j max f i 1 j f i 1 j W i V i 1 i n 1 j m 目标 f n m 2 f i 1 j W i V i 放第i件的价值 条件 j w i 1 f i 1 j 不放第i件物品获得的价值 主程序 fillchar f sizeof f 0 fori 1tondoforj 1tomdobeginf i j f i 1 j 不选择第i件物品if j w i and f i j f i 1 j w i v i 选择第i件物品 thenf i j f i 1 j w i v i end writeln f n m end 4 求最大连续子序列的和输入 第一行 n N 10000 第二行 n个整数 3000 3000 输出 最大连续子序列的和 样例 输入 7 64 132 32输出 8 算法1 枚举任意连续区间求和找最大值 readln n fori 1tondoread a i ans 30000000 fori 1tondoforj itondobeginsum 0 fork itojdosum sum a k ifsum ansthenans sum end writeln ans 时间 O n3 理想的算法 106 算法2 算法1的优化 readln n fori 1tondoread a i ans 30000000 fori 1tondobeginsum 0 forj itondobeginsum sum a j ifsum ansthenans sum end end writeln ans 时间 O n2 算法1和算法2是把n个数看作独立的没有联系的数来处理的 1 以a i 为结束点和以a i 1 为结束点的最大连续子序列有没有联系 有什么样的联系 2 f i 从第1项开始 以a i 为终点 右边界 的子序列的最大和 如果事先已经求得了以a i 为结束点的最大连续子序列和为f i 那么怎样求以a i 1 为结束点的最大连续子序列 64 132 32 算法3 a i 存储序列 f i 从第1项开始 以a i 为终点 右边界 的子序列的最大和 f i max f i 1 a i a i 即看f i 1 的正负初始 f 1 a 1 目标 max f i 1 i n proceduredp beginf 1 a 1 fori 2tondof i max f i 1 a i a i ans f 1 fori 2tondoiff i ansthenans f i end 时间 O n 在一个n m的方格中 m为奇数 放置有n m个数 如图 方格中间的下方有一人 此人可按照五个方向前进但不能越出方格 如所示 5取数 n m 100 方格数 100 100 样例输入 671643126034 56700260 1 236853400 27 17407 560 1341242 样例输出 51 f i j 人走到 i j 时得数的最大值 f i j max f i 1 j 2 f i 1 j 1 f i 1 j f i 1 j 1 f i 1 j 2 a i j proceduredp begink mdiv2 1 fori k 2tok 2dof n i a n i fori n 1downto1doforj max 1 k 2 i tomin k 2 i m dobeginf i j 10001 fork 2to2doif k j 1 and k jf i j thenf i j f i 1 k j f i j f i j a i j end ans f 1 1 fori 2tomdoiff 1 i ansthenans f 1 i writeln ans end 6迷宫寻宝一个n行m列的迷宫 1 1 输出 最大值 样例 输入2 54213 11 1 1 12 120 13125 11 12输出2 18 输入1 342 150513 16 18910输出1 33 分析 逐行扫描a i j 保存第i行第j列的宝藏价值 f i j 走到第i行第j列时所能收集的宝藏的最大价值 状态转移方程 f i j max f i 1 j f i j 1 a i j 1 1时 初始 f 1 1 a 1 1 目标 f n m functionmax a b integer integer beginmax a ifb athenmax b end proceduredp beginfillchar f sizeof f 0 fori 1tondoforj 1tomdoifa i j 1thenf i j max f i 1 j f i j 1 a i j end 读入数据的预处理 ifa i 1 j 1anda i j 1 1thena i j 1varf a array 0 maxn 0 maxm ofinteger 加边界 减少判断越界 readln n m fori 0ton 1do 初始全是障碍 forj 0tom 1doa i j 1 a 0 1 0 保证a 1 1 能到达 fori 1tondoforj 1tomdobeginread a i j if a i j 1 1 and a i 1 j 1 thena i j 1 end 342 150513 16 18910 某国为了防御敌国的导弹袭击 发展出一种导弹拦截系统 能发射任意发炮弹 但是这种导弹拦截系统有一个缺陷 虽然它的第一发炮弹能够到达任意的高度 但是以后每一发炮弹都要求高于前一发的高度 某天 雷达捕捉到敌国的导弹来袭 由于该系统还在试用阶段 所以只有一套系统 因此有可能不能拦截所有的导弹 输入敌国导弹依次飞来的高度 雷达给出的高度数据是不大于30000的正整数 计算这套系统最多能拦截多少导弹 7 拦截导弹 输入 第一行 n 1000 敌国导弹的数量 依次是敌国导弹的高度 30000 输出 最多拦截敌国导弹的数量 样例 输入 8271910123输出 4 转化 求最长的递增子序列长度 a i 保存数列的第i个数 f i 以a i 为结尾 a i 是最后一个元素 即包含a i 的最长递增子序列的序列长度 271910123 方法一 从前向后 f i max f j 1条件 1 j i并且a j a i 边界 f 1 1 目标 max f i 1 i n 输入 8271910123输出 4 f i 12134123 f 1 1 fori 2tondobeginf i 0 forj 1toi 1doif a j f i thenf i f j 找最大的f j f i f i 1 包括a i end max f 1 Fori 2tondoiff i maxthenmax f i writeln max end a i 保存数列的第i个数 f i 以a i 为开始 a i 是第一个元素 即包含a i 的最长递增子序列的序列长度 271910123 方法二 从后向前 f i max f j 1条件 i j n并且a i a j 边界 f n 1 目标 max f i 1 i n f n 1 max f n fori n 1downto1dobeginf i 0 forj i 1tondoif b i f i thenf i f j inc f i iff i maxthenmax f i end 怎样求最长递减子序列长度