信息学奥赛动态规划.pptVIP

* 动态规划 动态规划：在求一个大问题的时候，我们总是想方设法把它分成两个或多个更小的问题，然后分别解决每个小问题，在把各小问题的解答组合起来，即可得到原问题的解答，比如快速排序。然而常常有些问题难以用这类方法来做，因为子问题的数目太多，这样，如果把每个子问题再分解，必将得到更多的子问题，以至于最后解决问题需要耗费时间特别大。其实，在这类问题中，子问题的数目其实只是多项式，于是在上述算法中，一定有些子问题被重复计算多次。如果我们能够保存已解决的子问题的答案，而在需要的时简单查一下，这样我们就可以避免大量重复的计算，从而得到多项式时间的算法。 实现方法：用一个数组来记录所有已解决的子问题的答案。无论子问题以后是否被用到，只要它计算过，将其结果存入数组中，这种方法在程序设计中被称为动态规划。 比如: 【例题1】数字三角形问题。 ?????????????? 7 ????????????? 3 8 ???????????? 8 1 0 ??????????? 2 7 7 4 ?????????? 5 5 2 6 5 示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的正整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走。假设三角形行数≤100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总和最大，输出最大值。输人数据：由文件输入数据，文件第一行是三角形的行数N。以后的N行分别是从最顶层到最底层的每一层中的数字。如输入： 57???????????3 8 ????????8 1 0 ????2 7 7 4 ????4 5 2 6 5 ??输出：30 在这个问题中，如果我们每个子问题都去计算，就是穷举法了，但是我们可以用一个二维数组f[i,j]来表示从第一个点到走到(i,j)点的最大值，这样，我们在做下一个点(i+1,j)或者(i+1,j+1)的时候我们就可以使用到上面已经计算出来的f[i,j]了，这样就省去了很多计算，我们可以得到下面一个式子: f[i,j]:=f[i-1,j]+a[i,j] 最后我们求出max(f[n,j])即是我们要求的内容。 在这个动态规划中，我们用到的是从前往后的方法，以前讲的是从后往前的方法： 如果从后往前，我们就可以理解为 F[i,j]:=max(f[i+1,j]+a[i,j],f[i,j]+a[i,j]) 最后f[1,1]即是我们所求 【例题2】背包问题：一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。 输入文件：第一行输入一个数n（n100）,接下来n行，每行两位数，第一个数为该物品的重量，第二行为改物品的价值 输出文件：输出价值的最大数 同样的，在这个问题中，如果我们用穷举法去做这个问题就非常的复杂，而且非常的耗费时间，那么在这个问题中我们可以用一个一维数组f[j]去表示用空间j可以装下的最大的物品的最大价值。这时候怎么去动态呢？ 刚开始的时候我们可以理解f[j]都为0，即什么都没装，之后一个一个列举，当有一个物品的时候，f[j]怎么变化，然后有两个物品的时候怎么变化，直到全部列举完，这个过程就是一个动态的过程，即随着物品的不断增加，f[j]不断的变化 F[j]:=max(f[j],f[j-a[i]]+b[i]) 上一题是这f[i,j]这个阶段取决与f[i-1,j]这个阶段，同样的在这个题目中，当有n个物品的时候，你要怎么取舍，要取决与你前面保存的n-1个物品的状态 和这个问题类似的问题还有采药，开心的金明，几乎是一样的。 *