ACM+DP+算法++大集合

第 27 讲 贪心与动态规划贪心和动态规划在算法设计求解中均有着广泛的应用，因为它们都属于最优化问题的求解，因此这里将它们放在同一章节加以介绍。虽然都是求解最优化问题，但是贪心和动态规划还是有很大的区别的。前者是从问题的源出发每一步都采取最优的选择，最终找到问题的解；而后者则从考虑问题的子问题入手，通过比较划分后的独立子问题的解，来确定当前问题的最优解。相对而言，贪心法的形式非常多样，不容易对它做具体的分类，许多算法之中都蕴含了贪心的思想，而动态规划则可以大致分出一些应用较多的独立模型。因此在这一章节，我们会把笔墨侧重于后者。第一部分 贪心(Greedy)在求解最优化问题时，有这样一种自然的想法，希望每一步都则采取最优的策略，最终得到全局的最优解，这就是贪心思想。它的最大特点就是运行速度快，效率高，因此备受程序设计员的喜爱。当然，由此也带来了贪心法的最大问题，如何证明其正确性？因为在很多时候，局部最优解的选择往往最终得不到全局最优解。于是，我们在运用贪心思想解决问题时，就需要格外的小心。事实上，许多成熟的算法中都蕴含了贪心思想，比如求解最小生成树的Bellman-Ford 算法，单源最短路径的 Dijkstra 算法，求解二分图匹配的匈牙利算法等等。很多时候，贪心法虽然得不到最优解，但是仍具有重要的最用。比如，利用贪心法得到的近似解可以为搜索法提供较强的剪枝策略。就用一个例子来看看贪心法的应用吧：例 1, POJ 2287 田忌赛马田忌赛马的故事想必已经被大家所熟知了，孙膑“以君之下驷彼上驷，取君上驷与彼中驷，取君中驷与彼下驷”的策略使得田忌最终“一不胜而再胜”。如今，田忌与齐王决定再战一场，这一回双方决定用 n (n 1000)匹马较量一番。每一回合，先到的马将为主人赢得 200 美元，如果打平双方均无需指出。假设双方马匹的速度已给出，而田忌仍然能够提前知道齐王马匹的出场顺序，那么他最多能赢多少钱呢？分析 乍看下去，似乎没有很好的贪心思路，倒是可以利用二分图匹配的方法解题，可是时间复杂度相对较高，改进得的匈牙利算法也匹配需要 O（n 3）的时间，即使 Hopcraft 算法，也需要 O（ 2n）的时间复杂度。那么，真的不能运用贪心法吗？当年田忌获胜的方法或许能够给我们一些启迪。用下等马匹配齐王的上等马，虽然输掉了局部，却赢下了全局。也就是说，在最终的最优选择中，将有一些场次会输掉比赛。那么，既然是这样，我们何不学习田忌，用那些“下等马”输掉这些比赛，而让获胜者，均为齐王的“上等马”呢？这样的改进不会比原先的最优选择更差。设A n为田忌的马，且按速度排序 A1 > A2 > > An ,Bn为齐王的马，同样按速度排序 B1 > B2 > > Bn ,假设 Ap会输给它的对手，而 Aq（p q）则输给了它的对手，那么将再二者的对手对调，结果仍不会次于调换前。于是，调换后见下图：A1A2.An-1AnB1B2.Bn-1BnA1A2.An-1AnB1 红线代表输的场次B2 为了看得更清晰， . 红线间若有交叉可通过. 调整将其变为一组平行Bn-1 线，不会影响结果Bn图 1-1 最优策略 图 1-2 改进后既然改进前是最优策略，那么改进后它必然也是最优策略。而改进后的图与田忌赛马有着异曲同工之处，那么顺着它的思路，我们似乎又有了另一个改进策略。在图 1-2 中除去所有输掉比赛的A以及它们的对手，剩下的图中所有的“交叉”都可以去掉。即假设 Ap的对手为 Br,Aq的对手为 Bs，而 pq，那么我们可以对调双方的对手，显然结果不会变差。于是，改进后的图变成了如下： A1A2.An-1AnB1B2.Bn-1Bn图 1-3 最终策略显然，这个最终策略仍然是最优策略。于是，我们只需要枚举输掉的比赛场次，逐个判断是否满足上述策略的要求，就能够找到最优解。第二部分 动态规划（Dynamic Programming）动态规划是解决最优化问题的重要手段，它的优美精巧的结构特点深得程序设计员的喜爱，一段短小精悍的代码就能解决长长的回溯法所不能解决的问题，这是动态规划最吸引人的特点。动态规划是通过合并子问题的解来解决最优化问题的。许多时候，一个问题的若干子问题往往不是独立存在的，而和其它问题的子问题相同，于是对这些公共子问题的采取先计算求解并存值得方式，以便为将来反复调用时直接提供值，就成了动态规划的主体思想。可以看到，实现动态规划需要满足如下条件：1) 最优子结构性质，也就是说问题最优解与子问题的最优解有关。2) 无后效性，就是说问题的解只与已求得的子问题的解有关，与尚未求得的问题的解无关联。可以看到，这就需要问题的求解具有明显的层次性。因此，在求解此类问题时，我们需要将其划分成若干个层次，并找到层与层之间的关联，即“状态转移方程”。随后自底向上逐层求解。动态规划的一般形如：算法 2-1：for (用 i 枚举所有状态)for （用 j 枚举所有上层状态）利用状态 j 来更新状态 i 的最优值。下面来看一些动态规划的经典模型。1. 背包问题背包问题是动态规划问题中最为经典的模型之一，我们来看看它的简要描述：例 2 有一个能容积为 V 的背包，现在有 N 件物品，它们的容积和价值分别用An和B n表示，现在问如何选择物品放入背包，才能使背包在没有超载的情况下物品价值总和最大。分析 可以看到，背包中物品的顺序是没有要求的，因此我们可以逐个考虑每个物品。如果用一个一维数组C n记录考虑到当前物品 i 为止时，容积为 j(0 j V)的情况下，可以达到的最大价值为 Cj，那么状态转移方程如下：)0(, VjBMaxCiAjjj i 这里要注意两点，第一是公式中重量 j A(i)必须是一个在之前已经达到过了的可行解，否则 C(j A(i)是无效的，第二是 j 的循环顺序必须是从大到小，可以有效地防止在同一轮 i 的情况下，刚刚修改的 C(j-A(i)值对当前的C(j)产生影响。尽管背包问题还有不少变化的情况，但只要分析清楚层次，列出正确的转移方程，那么就能比较容易地解决它。2. 最长公共子串（LCS）问题最长公共子串问题同样是动态规划问题中的经典模型，再来看看它的简要描述：例 3 假设有两个字符串 A,B，求它们最长的公共子串 C。其中，“子串”的定义为，设 P = p1p2pm，那么串 Q 称为串 P 的长为 t“子串”，如果满足 Q = pq1pq2pqt，其中 1 t n, q1 < q2 < < qt。如果 C 既为 A 的子串，又为 B 的子串，那么就称 C 为 A 和 B 的公共子串。分析 先来看看一个例子，假设 A = acdefgad, B = bcaedafga c d e f g a db c a e d a f g它们的最长公共子串 C = aefg 或 cefg。可以看到，如果将 A 的最后一个字母去掉，并没有改变它们的最长公共子串，而如果将 B 的最后一个字母去掉，那么最长公共子串长就少了 1。原因在于，B 的最后一个字母 g 与 A 中的第 6 个字母 g 可匹配。于是我们考虑一般的情形：两个字符串求 LCS，如果它们的串尾均没有作出“贡献”，那么它们的 LCS 等价于删去串尾后两个字符串的 LCS；如果串尾有所“贡献”，那么要看着这个串尾是否相等。若相等，显然可将二者连线；反之，就要看哪个“贡献”对 LCS 更有帮助了。如果以 L(i, j)表示 A 串的前i 个字符和 B 串的前 j 个字符的最长公共子串长，那么刚才的文字描述用公式表示就是： BjAijiLMaxLjorijijijiji ,0,101,可以看到 L(i,j)的值只与 L(i-1，j),L（i，j-1）和 L(i-1，j-1)有关，这就具有明显的层次关系。按照上述转移方程就可求解最长公共子串的长。至于求出具体的串，那么只要在求解过程中记录下每一次的选择，最后根据最长串的串尾进行一遍倒推即可得到最长子串。3. 树型动态规划一个无环连通图便称为一棵树，由于树具有明显的层次关系，因此很多关于它的最优化问题都可以用动态规划的方法解决，可以把这一类方法归纳为树型动态规划。一些问题需要自己建立一颗树，再利用动态规划的方法解决，一些问题则本身就是以树为背景的。来看看下面这个例子：例 4, POJ1655给定一棵有 N(1 N 20000)个结点的树 T，定义结点的“平衡度”如下：删去该结点后，在剩下的结点构成的森林中，最大树的结点数。于是，我们的问题是，在树 T 中，找到平衡度最小的结点。分析 看完题目，最直接的想法自然是枚举每个点，然后求它的平衡度，也就是遍历这棵森林。但是，这种做法的时间复杂度至少是 O(N2)。对于如此大的N，这显然太慢了，有没有更好的方法呢？让我们再仔细分析一下，遍历一次树T，我们能得到多少信息。对于一个结点 A，必然是由某个结点 B 遍历过来，然后遍历它的所有后继 C、D。，如果我们能得到 A 的所有后继结点分别又遍历到了多少结点，那么我们就可以知道 B 结点之前已经遍历了多少结点，于是，所有与 A 有连接的结点块的信息便都得到了。那么也就求得了 A 的平衡度。如果用 Num(A)表示结点 A 和它的所有后继的个数，那么上述分析可用以下公式表示：)(Num1,ENum()Max的 后 继 结 点为的 平 衡 度利用上述公式，用 Dfs 对树进行一遍遍历就能找到平衡度最小结点的平衡度，稍加分析便可知，答案最多只有两个点。此外，此题的另一个要注意的问题便是如何保存这棵树。如果直接用邻接数组表示，那么内存消耗太大。一般有三种方法，一是用邻接链表保存，把所有与某个结点相邻的结点用一个链表串起来；二是将与结点 1,2,3,N 相邻的结点顺序的记录在一个数组中，然后为每个结点记录两个值，即与它相邻的结点在线形数组中的区间的端点；三是用 vector 容器保存。前两个方法都是利用了树是稀疏图，边数很少的性质来考虑的。4. 状态压缩动态规划有一些问题，我们无法用单独的状态运用动态规划，但是可是将一组状态合并为一个状态，并且合并以后可以看到明显的层次关系和最优子结构的性质，这样的手段就是状态压缩动态规划，一般简称状态 DP。许多时候由于单独的状态可以用 0 和 1 来表示，因此组合后的状态可以用一个普通的数的二进制形式来表示/ 由于计算机对二进制的表示和处理都非常方便，因此这样的手段为编写代码提供了很大的方便。例 5，POJ 2411给定一个 w×h(1w,h11)的矩形，如果用 1×2 的小矩形去拼装，那么共有多少种不同的拼法？分析 刚拿到这题时，可能大多数人的第一感觉是搜索题。可是仔细想想，最大的矩形面积超过了 100，用面积为 2 的方块去拼，显然方法数将是巨大的，搜索看来很难出解。那么有没有其它方法呢？用普通的动态规划考虑似乎也没有什么眉目，一个矩形与它的子矩形之间似乎很难找到什么有价值的关联。换个角度来想，当我们与小矩形去填充时，经常用的手段就是逐层填满，由于小矩形是 1×2 的，那么某一层的所有填充情况只可能遇上一层发生联系，因此，如果我们把一层看作一个状态，那么填充完它后，对于每一个小格，有两种可能，一是填充它的矩形一直顺延到了下一层，我们用状态 1 来表示，而是填充它的矩形没有顺延到下一层，我们用状态 0 来表示。把一层的状态连起来，我们就得到了一个状态组，形如 01110，这就是新的状态。如果每层有w 格，那么这样的状态组有 2w 种。 如果用 F(i,j)来表示达到第 i 层，第 j种状态的种类数，那么状态转移方程如下： k)1,-i(