网站建设公司哪个好呀金融网站建设,洛阳网站建设哪家公司好,wordpress 多媒体插件,广州网站公司推荐1. 介绍动态规划典型的被用于优化递归算法#xff0c;因为它们倾向于以指数的方式进行扩展。动态规划主要思想是将复杂问题(带有许多递归调用)分解为更小的子问题#xff0c;然后将它们保存到内存中#xff0c;这样我们就不必在每次使用它们时重新计算它们。要理解动态规划的…1. 介绍动态规划典型的被用于优化递归算法因为它们倾向于以指数的方式进行扩展。动态规划主要思想是将复杂问题(带有许多递归调用)分解为更小的子问题然后将它们保存到内存中这样我们就不必在每次使用它们时重新计算它们。要理解动态规划的概念我们需要熟悉一些主题什么是动态规划贪心算法简化的背包问题传统的背包问题Levenshtein DistanceLCS-最长的共同子序列利用动态规划的其他问题结论本文所有代码均为java代码实现。2. 什么是动态规划动态规划是一种编程原理可以通过将非常复杂的问题划分为更小的子问题来解决。这个原则与递归很类似但是与递归有一个关键点的不同就是每个不同的子问题只能被解决一次。为了理解动态规划我们首先需要理解递归关系的问题。每个单独的复杂问题可以被划分为很小的子问题这表示我们可以在这些问题之间构造一个递归关系。让我们来看一个我们所熟悉的例子斐波拉契数列斐波拉契数列的定义具有以下的递归关系注意递归关系是递归地定义下一项是先前项的函数的序列的等式。Fibonacci序列就是一个很好的例子。所以如果我们想要找到斐波拉契数列序列中的第n个数我们必须知道序列中第n个前面的两个数字。但是每次我们想要计算Fibonacci序列的不同元素时我们在递归调用中都有一些重复调用如下图所示我们计算Fibonacci(5)例如如果我们想计算F(5),明显的我们需要计算F(3)和F(4)作为计算F(5)的先决条件。然而为了计算F(4)我们需要计算F(3)和F(2)因此我们又需要计算F(2)和F(1)来得到F(3)其他的求解诸如此类。这样的话就会导致很多重复的计算这些重复计算本质上是冗余的并且明显的减慢了算法的效率。为了解决这种问题我们介绍动态规划。在这种方法中我们对解决方案进行建模就像我们要递归地解决它一样但我们从头开始解决它记忆到达顶部采取的子问题(子步骤)的解决方案。因此对于Fibonacci序列我们首先求解并记忆F(1)和F(2)然后使用两个记忆步骤计算F(3)依此类推。这意味着序列中每个单独元素的计算都是O(1)因为我们已经知道前两个元素。当使用动态规划解决问题的时候我们一般会采用下面三个步骤确定适用于所述问题的递归关系初始化内存、数组、矩阵的初始值确保当我们进行递归调用(可以访问子问题的答案)的时候它总是被提前解决。遵循这些规则让我们来看一下使用动态规划的算法的例子3. 贪心算法下面来以这个为例子Given a rod of length n and an array that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by cutting up the rod and selling the pieces.3.1. 对于没有经验的开发者可能会采取下面这种做法这个问题实际上是为动态规划量身定做的但是因为这是我们的第一个真实例子让我们看看运行这些代码会遇到多少问题public class naiveSolution { static int getValue(int[] values, int length) { if (length 0) return 0; int tmpMax -1; for (int i 0; i length; i) { tmpMax Math.max(tmpMax, values[i] getValue(values, length - i - 1)); } return tmpMax; } public static void main(String[] args) { int[] values new int[]{3, 7, 1, 3, 9}; int rodLength values.length; System.out.println(Max rod value: getValue(values, rodLength)); }}输出结果Max rod value: 17该解决方案虽然正确但效率非常低递归调用的结果没有保存所以每次有重叠解决方案时糟糕的代码不得不去解决相同的子问题。3.2.动态方法利用上面相同的基本原理添加记忆化并排除递归调用我们得到以下实现:public class dpSolution { static int getValue(int[] values, int rodLength) { int[] subSolutions new int[rodLength 1]; for (int i 1; i rodLength; i) { int tmpMax -1; for (int j 0; j i; j) tmpMax Math.max(tmpMax, values[j] subSolutions[i - j - 1]); subSolutions[i] tmpMax; } return subSolutions[rodLength]; } public static void main(String[] args) { int[] values new int[]{3, 7, 1, 3, 9}; int rodLength values.length; System.out.println(Max rod value: getValue(values, rodLength)); }}输出结果Max rod value: 17正如我们所看到的的输出结果是一样的所不同的是时间和空间复杂度。通过从头开始解决子问题我们消除了递归调用的需要利用已解决给定问题的所有先前子问题的事实。性能的提升为了给出动态方法效率更高的观点的证据让我们尝试使用30个值来运行该算法。 一种算法需要大约5.2秒来执行而动态解决方法需要大约0.000095秒来执行。4. 简化的背包问题简化的背包问题是一个优化问题没有一个解决方案。这个问题的问题是 - “解决方案是否存在”Given a set of items, each with a weight w1, w2... determine the number of each item to put in a knapsack so that the total weight is less than or equal to a given limit K.给定一组物品每个物品的重量为w1w2 …确定放入背包中的每个物品的数量以使总重量小于或等于给定的极限K首先让我们把元素的所有权重存储在W数组中。接下来假设有n个项目我们将使用从1到n的数字枚举它们因此第i个项目的权重为W [i]。我们将形成(n 1)x(K 1)维的矩阵M。M [x] [y]对应于背包问题的解决方案但仅包括起始数组的前x个项并且最大容量为y例如假设我们有3个元素权重分别是w12kg,w23kg,w34kg。利用上面的方法我们可以说M [1] [2]是一个有效的解决方案。这意味着我们正在尝试用重量阵列中的第一个项目(w1)填充容量为2kg的背包。在M [3] [5]中我们尝试使用重量阵列的前3项(w1w2w3)填充容量为5kg的背包。这不是一个有效的解决方案因为我们过度拟合它。4.1. 矩阵初始化当初始化矩阵的时候有两点需要注意Does a solution exist for the given subproblem (M[x][y].exists) AND does the given solution include the latest item added to the array (M[x][y].includes).给定子问题是否存在解(M [x] [y] .exists)并且给定解包括添加到数组的最新项(M [x] [y] .includes)。因此初始化矩阵是相当容易的M[0][k].exists总是false如果k0因为我们没有把任何物品放在带有k容量的背包里。另一方面M[0][0].exists true,当k0的时候背包应该是空的因此我们在里面没有放任何东西这个是一个有效的解决方案。此外我们可以说M[k][0].exists true但是对于每个k来说 M[k][0].includes false。注意仅仅因为对于给定的M [x] [y]存在解决方案它并不一定意味着该特定组合是解决方案。在M [10] [0]的情况下存在一种解决方案 - 不包括10个元素中的任何一个。这就是M [10] [0] .exists true但M [10] [0] .includes false的原因。4.2.算法原则接下来让我们使用以下伪代码构造M [i] [k]的递归关系if (M[i-1][k].exists True): M[i][k].exists True M[i][k].includes Falseelif (k-W[i]0): if(M[i-1][k-W[i]].exists true): M[i][k].exists True M[i][k].includes Trueelse: M[i][k].exists False因此解决方案的要点是将子问题分为两种情况:对于容量k,当存在第一个i-1元素的解决方案对于容量k-W [i],当第一个i-1元素存在解决方案第一种情况是不言自明的我们已经有了问题的解决方案。第二种情况是指了解第一个i-1元素的解决方案但是容量只有一个第i个元素不满这意味着我们可以添加一个第i个元素并且我们有一个新的解决方案4.3. 实现下面这何种实现方式使得事情变得更加容易我们创建了一个类Element来存储元素public class Element { private boolean exists; private boolean includes; public Element(boolean exists, boolean includes) { this.exists exists; this.includes includes; } public Element(boolean exists) { this.exists exists; this.includes false; } public boolean isExists() { return exists; } public void setExists(boolean exists) { this.exists exists; } public boolean isIncludes() { return includes; } public void setIncludes(boolean includes) { this.includes includes; }}接着我们可以深入了解主要的类public class Knapsack { public static void main(String[] args) { Scanner scanner new Scanner (System.in); System.out.println(Insert knapsack capacity:); int k scanner.nextInt(); System.out.println(Insert number of items:); int n scanner.nextInt(); System.out.println(Insert weights: ); int[] weights new int[n 1]; for (int i 1; i n; i) { weights[i] scanner.nextInt(); } Element[][] elementMatrix new Element[n 1][k 1]; elementMatrix[0][0] new Element(true); for (int i 1; i k; i) { elementMatrix[0][i] new Element(false); } for (int i 1; i n; i) { for (int j 0; j k; j) { elementMatrix[i][j] new Element(false); if (elementMatrix[i - 1][j].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(false); } else if (j weights[i]) { if (elementMatrix[i - 1][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); } } } } System.out.println(elementMatrix[n][k].isExists()); }}唯一剩下的就是解决方案的重建在上面的类中我们知道解决方案是存在的但是我们不知道它是什么。为了重建我们使用下面的代码List solution new ArrayList(n);if (elementMatrix[n][k].isExists()) { int i n; int j k; while (j 0 i 0) { if (elementMatrix[i][j].isIncludes()) { solution.add(i); j j - weights[i]; } i i - 1; }}System.out.println(The elements with the following indexes are in the solution: (solution.toString())); 输出Insert knapsack capacity: 12 Insert number of items: 5 Insert weights: 9 7 4 10 3 true The elements with the following indexes are in the solution: [5, 1]背包问题的一个简单变化是在没有价值优化的情况下填充背包但现在每个单独项目的数量无限。通过对现有代码进行简单调整可以解决这种变化// Old code for simplified knapsack problemelse if (j weights[i]) { if (elementMatrix[i - 1][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); }}// New code, note that were searching for a solution in the same// row (i-th row), which means were looking for a solution that// already has some number of i-th elements (including 0) in its solutionelse if (j weights[i]) { if (elementMatrix[i][j - weights[i]].isExists()) { elementMatrix[i][j].setExists(true); elementMatrix[i][j].setIncludes(true); }}5. 传统的背包问题利用以前的两种变体现在让我们来看看传统的背包问题看看它与简化版本的不同之处Given a set of items, each with a weight w1, w2... and a value v1, v2... determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit k and the total value is as large as possible.在简化版中每个解决方案都同样出色。但是现在我们有一个找到最佳解决方案的标准(也就是可能的最大值)。请记住这次我们每个项目都有无限数量因此项目可以在解决方案中多次出现。在实现中我们将使用旧的类Element其中添加了私有字段value用于存储给定子问题的最大可能值:public class Element { private boolean exists; private boolean includes; private int value; // appropriate constructors, getters and setters}实现非常相似唯一的区别是现在我们必须根据结果值选择最佳解决方案public static void main(String[] args) { // Same code as before with the addition of the values[] array System.out.println(Insert values: ); int[] values new int[n 1]; for (int i1; i n; i) { values[i] scanner.nextInt(); } Element[][] elementMatrix new Element[n 1][k 1]; // A matrix that indicates how many newest objects are used // in the optimal solution. // Example: contains[5][10] indicates how many objects with // the weight of W[5] are contained in the optimal solution // for a knapsack of capacity K10 int[][] contains new int[n 1][k 1]; elementMatrix[0][0] new Element(0); for (int i 1; i n; i) { elementMatrix[i][0] new Element(0); contains[i][0] 0; } for (int i 1; i k; i) { elementMatrix[0][i] new Element(0); contains[0][i] 0; } for (int i 1; i n; i) { for (int j 0; j k; j) { elementMatrix[i][j] new Element(elementMatrix[i - 1][j].getValue()); contains[i][j] 0; elementMatrix[i][j].setIncludes(false); elementMatrix[i][j].setValue(M[i - 1][j].getValue()); if (j weights[i]) { if ((elementMatrix[i][j - weights[i]].getValue() 0 || j weights[i])) { if (elementMatrix[i][j - weights[i]].getValue() values[i] M[i][j].getValue()) { elementMatrix[i][j].setIncludes(true); elementMatrix[i][j].setValue(M[i][j - weights[i]].getValue() values[i]); contains[i][j] contains[i][j - weights[i]] 1; } } } System.out.print(elementMatrix[i][j].getValue() / contains[i][j] ); } System.out.println(); } System.out.println(Value: elementMatrix[n][k].getValue());}输出Insert knapsack capacity: 12 Insert number of items: 5 Insert weights: 9 7 4 10 3 Insert values: 1 2 3 4 5 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 1/1 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 2/1 0/0 1/0 0/0 0/0 0/0 0/0 0/0 0/0 0/0 3/1 0/0 0/0 2/0 6/2 1/0 0/0 5/1 9/3 0/0 0/0 0/0 0/0 3/0 0/0 0/0 2/0 6/0 1/0 4/1 5/0 9/0 0/0 0/0 0/0 5/1 3/0 0/0 10/2 8/1 6/0 15/3 13/2 11/1 20/4 Value: 20 6. Levenshtein Distance另一个使用动态规划的非常好的例子是Edit Distance或Levenshtein Distance。Levenshtein Distance就是两个字符串A,B,我们需要使用原子操作将A转换为B字符串删除字符串插入字符替换(从技术上讲它不止一个操作但为了简单起见我们称之为原子操作)这个问题是通过有条理地解决起始字符串的子串的问题来处理的逐渐增加子字符串的大小直到它们等于起始字符串。我们用于此问题的递归关系如下如果a b则c(ab)为0如果a b则c(ab)为1。实现public class editDistance { public static void main(String[] args) { String s1, s2; Scanner scanner new Scanner(System.in); System.out.println(Insert first string:); s1 scanner.next(); System.out.println(Insert second string:); s2 scanner.next(); int n, m; n s1.length(); m s2.length(); // Matrix of substring edit distances // example: distance[a][b] is the edit distance // of the first a letters of s1 and b letters of s2 int[][] distance new int[n 1][m 1]; // Matrix initialization: // If we want to turn any string into an empty string // the fastest way no doubt is to just delete // every letter individually. // The same principle applies if we have to turn an empty string // into a non empty string, we just add appropriate letters // until the strings are equal. for (int i 0; i n; i) { distance[i][0] i; } for (int j 0; j n; j) { distance[0][j] j; } // Variables for storing potential values of current edit distance int e1, e2, e3, min; for (int i 1; i n; i) { for (int j 1; j m; j) { e1 distance[i - 1][j] 1; e2 distance[i][j - 1] 1; if (s1.charAt(i - 1) s2.charAt(j - 1)) { e3 distance[i - 1][j - 1]; } else { e3 distance[i - 1][j - 1] 1; } min Math.min(e1, e2); min Math.min(min, e3); distance[i][j] min; } } System.out.println(Edit distance of s1 and s2 is: distance[n][m]); }}输出Insert first string: man Insert second string: machine Edit distance of s1 and s2 is: 3 如果你想了解更多关于Levenshtein Distance的解决方案我们在另外的一篇文章中用python实现了 Levenshtein Distance and Text Similarity in Python使用这个逻辑我们可以将许多字符串比较算法归结为简单的递归关系它使用Levenshtein Distance的基本公式7. 最长共同子序列(LCS)这个问题描述如下Given two sequences, find the length of the longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous.给定两个序列找到两个序列中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列但不一定是连续的.阐明如果我们有两个字符串s1MICE和s2MINCE
