洋葱数学,你曾经在Java中使用过动态编程吗?-ope电竞-ope电竞平台-ope电竞投注

好莱坞在线 195℃ 0

1. 介绍

动态规划典型的被用于优化递归算法,由于它们倾向于以指数的办法进行扩展。动态规划首要思维是将复杂问题(带有许多递归调用)分解为更小的子问题,然后将它们保存到内存中,这样咱们就不用在每次使消化体系用它们时从头核算它们。

要了解动态规划的概念,咱们需求了解一些主题:

  1. 什么是动态规划?
  2. 贪心算法
  3. 简化的背包问题
  4. 传统的背包问题
  5. LCS-最长的一起子序列
  6. 运用动态规划的其他问题
  7. 定论

本文一切代码均为java代码完成。

2. 什么是动态规划?

动态规划是一种编程原理,能够经过将十分复杂的问题划分为更小的子问题来处理。这个准则与递归很类似,可是与递归有一个要害点的不同,便是每个不同的子问题只能被处理一次。

为了了解动态规划,咱们首要需求了解递归联系的问题。每个独自的复杂问题能够被划分为很小的子问题,这表明咱们能够在这些问题之间结构一个递归联系。让咱们来看一个咱们所了解的比如:斐波拉契数列,斐波拉契数列的界说具有以下的递归联系:

留意:递归联系是递归地界说下一项是从前项的函数的序列的等式。Fibonacci序列洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注便是一个很好的比如。

所以,假如咱们想要找到斐波拉契数列序列中的第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),由于咱们现已知道前两个元素。

当运用动态规划处理问题的时分,咱们一般会选用下面三个过程:

  1. 确认适用于所述问题的递归联系
  2. 初始化内存、数组、矩阵的初始值
  3. 保证当咱们进行递归调用(能够拜访子问题的答案)的时分它总是被提早处理。

遵从这些规矩,让咱们来看一下运用动态规划的算法的比如:

3. 贪心算法

下面来以这个为比如:


Given a rod of length n and an array that contain好好学习s 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.

给定一组物品,每个物品的分量为w1,w2 ......确认放入背包中的每个物品的数量,以使总分量小于或等于给定的极限K

首要让咱们把元素的一切权重存储在W数组中。接下来,假定有n个项目,咱们将运用从1到n的数字枚举它们,因而第i个项目的权重为W [i]。咱们将构成(n + 1)x(K + 1)维罗永浩激辩王自若的矩阵M。M [x] [y]对应于背包问题的处理计划,但仅包含开始数组的前x个项,而且最大容量为y

例如

假定咱们有3个元素,权重分别是w1=2kg,w2=3kg,w3=4kg。运用上面的办法,咱们能够说M [1] [2]是一个瑞金有用的处理计划。这意味着咱们正在测验用分量阵列中的第一个项目(w1)填充容量为2kg的背包。

在M [3] [5]中,咱们测验运用分量阵列的前3项(w1,w2,w3)填充容量为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,假如k>0,由于咱们没有把任何物品放在带有k容量的背包里。

另一方面,M[0][0].exists = true,当k=0的时分,背包应该是空的,因而咱们在里面没有放任何东西,这个是一个有用的处理计划。

此外,咱们能够说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] .include在那悠远的当地s = false的原因。

4.2.算法准则

接下来,让咱们运用以下伪代码结构M [i] [k]的递归联系:


if (M[i-1][k].exists == True): 
M[i][k].exists = True
M[i][k].includes = False
elif (k-W[i]>=0):
if(M[i-1][k-W[i]].exists == true):
M[i][k].exists = True
M[i][k].includes = True
else:
M[i][k].exists = False

因而,处理计划的关键是将子问题分为两种状况:

  1. 关于容量k,当存在第一个i-1元素的处理计划
  2. 关于容量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;
}洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注
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 =洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注 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);
elementMat查看rix[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:\n" + (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 problem
else i科罗娜f (j >= weights[i]) {
if (elementMatrix[i - 1][j - weights[i]].isExists()) {
elementMatrix[i][j].洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注setExists(true);
elementMatrix[i][j].setIncludes(true);
}
}
// New code, note that we're searching for a solution in the same
// row (i-th row), which means we're looking for a solution that
// already has some number of i-th elements (including 0) in it's solution
else 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.

在简化版中,每个处理计划都相同超卓。可是,现在咱们有一个找到最佳处理计划的规范(也便是或许的最大值)苹果手机开不了机怎么办。请记住,这次咱们每个项目都有无限数量,因而项目能够在处理douban计划中屡次呈现。

在完成中,咱们将运用旧的类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 i=1; 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 K=1洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注0
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 - w恩山eights[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:

  1. 字符串删去
  2. 字符串刺进
  3. 字符替换(从技术上讲,它不止一个操作,但为了简略起见,咱们称之为原子操作)

这个问题是经过有条理地处理开始字符串的子串的问题来处理的,逐步添加子字符串的巨细,直到它们等于开始字符串。

咱们用于此问题的递归联系如下:

假如a == b则c(a,b)为0,假如a = = b则c(a,b)为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
// exa哈尔滨杀人犯赵志mple: distance[a][b] is the edit distance
// of the first a letters of s1 and b letters of 洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注s2
int[][] di孝猴stance = 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 st才智oring 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.

给定两个序列,找到两个序列中存在的最长子序列的长度。子序列是以相同的相对次序呈现的序列,但不一定是接连的.

说明:

假如咱们有两个字符串s1="MICE"和s2="MINCE",最长的一起子序列是MI或许CE。可是,最长的公共子序列将是“MICE”,由于成果子序列的元素不用是接连的次序。

递归联系与一般逻辑:

咱们能够看到,Levenshtein distance和LCS之间只要细小的不同,特别是移动本钱。

在LCS中,咱们没有字符刺进和字符删去的本钱,这意味着咱们只核算字符替换(对角线移动)的本钱,假如两个当时字符串字符a [i]和b [j] 是相同的,则本钱为1。

LCS的终究本钱是2个字符串的最长子序列的长度,这正是咱们所需求的。

Using this logic, we can boil down a lot of string comparison algorithms to simple recurrence relations which utilize the base formula of the Levenshtein distance

运用这个逻辑,咱们能够将许多字符串比较算法归结为简略的递归联系,它运用Levenshtein 重生之温婉distance的根本公式。

完成:


public class LCS { 
public static void main(String[] args) {
String s1 = new String("Hillfinger");
String s2 = new String("Hilfiger");
int n = s1.length();
int m = s2.length();
int[][] solutionMatrix = new int[n+1][m+1];
for (int i = 0; i < n; i++) {
solutionMatrix[i][0] = 0;
}
for (int i = 0; i < m; i++) {
solutionMatrix[0][i] = 0;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int max1, max2, max3;
max1 = solutionMatrix[i -龙拳小子 1][j];
max2 = solutionMatrix[i][j - 1];
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
max3 = solutionMatrix[i - 1][j - 1] + 1;
} else {
max3 = solutionMatrix[i - 1][j - 1];
}
int tmp = Math.max(max1, max2);
solutionMatrix[i][j] = Math.max(tmp, max3);
}
}
System.out.println("Length of longest continuous subsequence: " + solutionMatrix[n][m]);
}
}

输出:


Length of longest continuous subsequence: 8

8.运用动态规划的其他问题

运用动态规划能够处理许多问题,下面列举了一些:

  1. 分区问题:给定一组整数,找出它是否能够分红两个具有持平和的子集
  2. 子集和问题:给你一个正整数的数组及元素还有一个算计值,是否在数组中存在一个子集的的元素之和等于算计值。
  3. 硬币改变问题:鉴于给定面额的硬币无限供给,找到取得所需改变的不同办法的总数
  4. k变量线性方程的一切或许的解:给定k个变量的线性方程,核算它的或许解的总数
  5. 找到醉汉不会从山崖上掉下来的概率:给定一个线性空间代表间隔山崖的间隔,让你知道酒鬼从山崖开始的间隔,以及他向山崖p行进并远离山崖1-p的倾向,核算出他的生计概率

9.定论

动态编程是一种东西,能够节约很多的核算时刻,以交换更大的空间复杂性,这在很大程度上取决于您正在处理的洋葱数学,你曾经在Java中运用过动态编程吗?-ope电竞-ope电竞渠道-ope电竞投注体系类型,假如CPU时刻很名贵,您挑选消耗内存的处理计划,另一方面,假如您的内存有限,则挑选更耗时的处理计划。

来历:大众号「锅外的大佬」

标签: 老虎机