动态规划入门-系列解题报告.doc

动态规划入门 系列解题报告 作者：周娟 时间：2010-5-30 例题： /diy/contest_show.php?cid=6533 组题讲解 安晓冲 1001 City Game hdu1505 矩阵中的最大子段和问题 1006 Dining Cows 1009 Bookshelf2 1010 Charm Bracelet Pku 3624 01背包 （1）1002 Exact Change （2）1003 Rhyme Schemes （3）1004 CowRoller Coaster （4）1005 Corn Fields （5）1007 Anniversary party （6）1008 Cow Exhibition hdu 1231 最大连续子序列 最大子段和问题 Hdu 1003 Max Sum 最大子段和问题 Hdu 1081 To The Max 矩阵中的最大子段和问题 （7）Pku 1384 Piggy-Bank （8）Pku 2626 CHESS （9）Pku 2559 Largest Rectangle in a Histogram （10）Pku 2796 Feel Good /JudgeOnline/problem?id=2559 12/JudgeOnline/problem?id=1384 Piggy-Bank 12/JudgeOnline/problem?id=2626 CHESS 以上绿色的，在本文中给出了较完整的解题报告，部分由程道雷同学提供。在今天的动态规划专题讲座中，安晓冲同学组题的10道，在hdu上的DIY上，并对它们进行了较详细的讲解。 作业要求：以上黑色的尚未给出解题报告，我在其左边给出了编号（n）,假如你的学号是m,那么满足条件m%3==n%3的题号nx,你需要写出这些题目的解题报告来，可以像本文这样即有word又有ppt.这样每个人写3到4个。时间两周之内。令d=n%3,写完好统一交给下面的指定同学。 d 收集者 0 程道雷 1 袁传顺 2 彭建欢 由收集者整理，并综合的写出该题优秀的解题报告。 当然，除了要完成较完整解题报告的，这里列出的所有黑色和绿色的题目，你们都需要练习并掌握。 本文最后给出 了 各类型 动态规划 练习题的 题号，大家也可以从网上获取。 目录 P01: 01背包问题 3 题目 3 基本思路 3 优化空间复杂度 3 初始化的细节问题 4 一个常数优化 5 小结 5 Pku 3624 Charm Bracelet 5 背包问题九讲 8 hdu 1231最大连续子序列 10 Hdu 1003 Max Sum 12 Hdu 1081 To The Max 17 Diy 1001 City Game 18 diy 1006 Dining Cows 21 Diy 1009 Bookshelf 2 23 Pku 2559 Largest Rectangle in a Histogram 26 各类型 动态规划 练习题 27  P01: 01背包问题 题目 有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。 基本思路 这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。 用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是： f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 这个方程非常重要，基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。 优化空间复杂度 以上方法的时间和空间复杂度均为O(VN)，其中时间复杂度应该已经不能再优化了，但空间复杂度却可以优化到O。 先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f