备案控制台
探索云世界
开发者社区 人工智能 文章 正文

【算法设计与分析】——动态规划算法

2024-03-06 52
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【算法设计与分析】——动态规划算法

🎯内容概括：

1）矩阵连乘问题：已知矩阵A1A2A3A4A5 ，使用向量P<P0=3，P1=2，P2=5，P3=10，P4=2，P5=3>存储行列，求出相乘次数最少的加括号位置。


2）0-1背包问题：有5个物品，其重量分别为{2,2,6,5,4}，价值分别为{6,3,5,4,6}。背包容量为10，物品不可分割，求装入背包的物品和获得的最大价值。


3）最长公共子序列问题：求X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}的最长公共子序列。


🎯目的：

1）了解动态规划算法思想；


2）掌握算法的基本要素及解题步骤；


3）能够对实际问题，能够按照动态规划解题步骤，分析问题；


4）能够正确的编码、实现动态规划算法；


5）能够正确分析算法的时间复杂度和空间复杂度。


🎯基本步骤：

1）审阅题目，明确题目的已知条件和求解的目标；


2）问题建模；


3）算法设计；


4）编码实现(语言不限)；


5）测试数据；


6）程序运行结果；


7）分析实验结果是否符合预期，如果不符合，分析可能的原因；


8）算法分析。


🎯环境：

VC6.0 / Eclipse / Pycharm。


🎯内容：

💻one：

🎃问题：

1）矩阵连乘问题：已知矩阵A1A2A3A4A5 ，使用向量P<P0=3，P1=2，P2=5，P3=10，P4=2，P5=3>存储行列，求出相乘次数最少的加括号位置。


🎃解题思路：

1.创建两个二维数组m和s，其中m[i][j]表示从矩阵Ai到Aj的连乘所需的最少次数，s[i][j]表示从矩阵Ai到Aj的连乘的最优加括号位置。

2.初始化m[i][i]为0，表示单个矩阵相乘的次数为0。

3.对于长度l=2到n的子链长度，依次计算m[i][j]和s[i][j]

  • 遍历每个可能的分割点k，计算m[i][j]的值。
  • m[i][j]的值等于m[i][k] + m[k+1][j] + Pi-1 * Pk * Pj。
  • 更新m[i][j]时，同时更新s[i][j]为k，表示在Ai到Aj之间最优的加括号位置是在矩阵Ak与Ak+1之间。

    4.最终，m[1][n]存储的即为从A1到An连乘的最小次数。


🎃代码分析：

matrix1 方法:

public static void matrix1(int[] p) {
    int n = p.length - 1;
    int[][] x = new int[n][n];
    int[][] y = new int[n][n];
 
    for (int l = 2; l <= n; l++) {
        for (int i = 0; i < n - l + 1; i++) {
            int j = i + l - 1;
            x[i][j] = Integer.MAX_VALUE;
            for (int k = i; k < j; k++) {
                int q = x[i][k] + x[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
                if (q < x[i][j]) {
                    x[i][j] = q;
                    y[i][j] = k;
                }
            }
        }
    }
    System.out.println("相乘次数最少的加括号的位置为：");
    print(y, 0, n - 1);
    System.out.println();
    System.out.println("最少相乘次数：" + x[0][n - 1]);
}

这个方法使用动态规划来解决矩阵链乘问题。它通过填充二维数组 x 和 y 来计算最少相乘次数和最优加括号位置。

print 方法:


public static void print(int[][] s, int i, int j) {
    if (i == j) {
        System.out.print("A" + (i + 1));
    } else {
        System.out.print("(");
        print(s, i, s[i][j]);
        print(s, s[i][j] + 1, j);
        System.out.print(")");
    }
}

这个方法用于打印最优加括号位置。根据数组 s 中存储的最优加括号位置信息，递归地打印出最优的加括号位置。

main 方法:

public static void main(String[] args) {
    int[] m = { 3, 2, 5, 10, 2, 3 };
    matrix1(m);
}

这是程序的入口，在这里创建了一个整型数组 m，表示矩阵的维度。然后调用 matrix1 方法来解决矩阵连乘问题。

🎃总代码：

package test20210110;
 
public class Test01 {
  public static void matrix1(int[] p) {
    int n = p.length - 1;
    int[][] x = new int[n][n];
    int[][] y = new int[n][n];
 
    for (int l = 2; l <= n; l++) {
      for (int i = 0; i < n - l + 1; i++) {
        int j = i + l - 1;
        x[i][j] = Integer.MAX_VALUE;
        for (int k = i; k < j; k++) {
          int q = x[i][k] + x[k + 1][j] + p[i] * p[k + 1] * p[j + 1];
          if (q < x[i][j]) {
            x[i][j] = q;
            y[i][j] = k;
          }
        }
      }
    }
    System.out.println("相乘次数最少的加括号的位置为：");
    print(y, 0, n - 1);
    System.out.println();
    System.out.println("最少相乘次数：" + x[0][n - 1]);
  }
  public static void print(int[][] s, int i, int j) {
    if (i == j) {
      System.out.print("A" +(i+1));
    } else {
      System.out.print("(");
      print(s, i, s[i][j]);
      print(s, s[i][j] + 1, j);
      System.out.print(")");
    }
  }
 
  public static void main(String[] args) {
    int[] m = { 3, 2, 5, 10, 2, 3 };
    matrix1(m);
  }
}

🎃 运行截图：

💻two：

🎃问题：

2）0-1背包问题：有5个物品，其重量分别为{2,2,6,5,4}，价值分别为{6,3,5,4,6}。背包容量为10，物品不可分割，求装入背包的物品和获得的最大价值。

🎃解题思路：

首先，定义一个二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，背包容量为 j 时能够获得的最大价值。


然后，初始化边界条件。当没有物品可选或者背包容量为0时，最大价值都为0。因此，可以将 dp[0][j] 和 dp[i][0]（其中0 ≤ i ≤ 5，0 ≤ j ≤ 10）都设置为0。


接下来，通过两层循环遍历物品和背包容量。外层循环表示当前所选物品的数量，从1到5；内层循环表示背包容量，从1到10。


在每次迭代中，分为两种情况进行考虑：


  1. 若当前物品重量大于当前背包容量，则无法选择该物品，因此 dp[i][j] 的值与 dp[i-1][j] 相等。
  2. 若当前物品重量小于等于当前背包容量，则需要进行选择。可以比较将该物品放入背包后的总价值与不放入该物品的总价值，选择其中较大的一个。即 dp[i][j] 的值为 max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])，其中 w[i] 表示第 i 个物品的重量，v[i] 表示第 i 个物品的价值。

完成所有的循环后，dp[5][10] 中存储的即为装入背包的物品能够获得的最大价值。


🎃代码分析：

首先，定义了一个 Value 类，并在 main 方法中编写了解决0-1背包问题的代码。

int[] weight = { 2, 2, 6, 5, 4 };
int[] value = { 6, 3, 5, 4, 6 };
int a = 10;
 
int[][] dp = new int[weight.length + 1][a + 1];

以上代码定义了物品的重量数组 weight、价值数组 value 和背包容量 a。同时，创建了一个二维数组 dp，大小为 (weight.length + 1) × (a + 1)，用于存储状态转移的结果。 

for (int i = 1; i <= weight.length; i++) {
    for (int j = 1; j <= a; j++) {
        if (j >= weight[i - 1]) {
            dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
        } else {
            dp[i][j] = dp[i - 1][j];
        }
    }
}

以上代码通过两层循环遍历物品和背包容量，实现了动态规划的过程。在每次迭代中，根据当前物品重量和背包容量的大小关系，选择将该物品放入背包还是不放入背包，并更新 dp 数组中相应位置的值。


具体而言，如果当前物品的重量小于等于背包容量，则需要考虑将该物品放入背包后是否能够获得更大的总价值。通过比较不放入该物品和放入该物品两种情况下的总价值，选择其中较大的一个，并更新 dp[i][j] 的值。


如果当前物品的重量大于背包容量，则无法放入该物品，直接将 dp[i][j] 的值设为上一个状态 dp[i-1][j] 的值。

System.out.print("装入的物品是第");
int i = weight.length;
int j = a;
while (i > 0 && j > 0) {
    if (dp[i][j] != dp[i - 1][j]) {
        System.out.print(i + "个,");
        j -= weight[i - 1];
    }
    i--;
}
 
System.out.println("\n最大价值为：" + dp[weight.length][a]);

以上代码用于输出装入背包的物品和获得的最大价值。通过回溯的方式，从 dp 数组中找到装入背包的物品。具体来说，从右下角开始遍历 dp 数组，如果当前位置的值不等于上一个状态的值，说明选择了第 i 个物品放入背包，输出 i 并更新背包容量 j。然后，向左上方移动，继续遍历。


最后，输出最大价值，即 dp[weight.length][a] 的值。


🎃总代码：

package one;
 
public class Value {
 
  public static void main(String[] args) {
    int[] weight = { 2, 2, 6, 5, 4 };
    int[] value = { 6, 3, 5, 4, 6 };
    int a = 10;
 
    int[][] dp = new int[weight.length + 1][a + 1];
 
    for (int i = 1; i <= weight.length; i++) {
      for (int j = 1; j <=a; j++) {
        if (j >= weight[i - 1]) {
          dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
        } else {
          dp[i][j] = dp[i - 1][j];
        }
      }
    }
    System.out.print("装入的物品是第");
    int i = weight.length;
    int j = a;
    while (i > 0 && j > 0) {
      if (dp[i][j] != dp[i - 1][j]) {
        System.out.print(i + "个,");
        j -= weight[i - 1];
      }
      i--;
    }
    
    System.out.println("\n最大价值为：" + dp[weight.length][a]);
  }
}

🎃运行截图：

💻three：

🎃问题：

最长公共子序列问题：求X={A,B,C,B,D,A,B}和Y={B,D,C,A,B,A}的最长公共子序列。

🎃解题思路：

最长公共子序列（Longest Common Subsequence，LCS）问题是经典的动态规划问题之一。给定两个序列 X 和 Y，找出它们的最长公共子序列的长度。


对于序列 X={A,B,C,B,D,A,B} 和 Y={B,D,C,A,B,A}，可以采用动态规划的方法来解决最长公共子序列问题。下面是解题的思路和步骤：


1.定义状态： 创建一个二维数组 dp，其中 dp[i][j] 表示序列 X 的前 i 个元素与序列 Y 的前 j 个元素的最长公共子序列的长度。


2.状态转移方程： 根据动态规划的性质，我们可以使用以下状态转移方程来计算 dp[i][j]：


  1. 如果 X[i-1] == Y[j-1]，即序列 X 的第 i-1 个元素和序列 Y 的第 j-1 个元素相等，那么 dp[i][j] = dp[i-1][j-1] + 1，表示当前这对匹配的字符可以贡献到最长公共子序列的长度中。
  2. 如果 X[i-1] != Y[j-1]，即序列 X 的第 i-1 个元素和序列 Y 的第 j-1 个元素不相等，那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示当前位置的最长公共子序列长度取决于去掉 X 的最后一个元素时和去掉 Y 的最后一个元素时哪个更长。


3.初始化边界条件： 对于 dp 数组的第一行和第一列，因为其中一个序列为空时，最长公共子序列的长度必定为 0，所以将其初始化为 0。


4.填充表格： 根据状态转移方程，从 dp[0][0] 开始，逐行或逐列填充 dp 数组，直到填满整个表格。


5.回溯求解： 最后根据填充好的 dp 数组，可以进行回溯来找到具体的最长公共子序列。


通过以上步骤，就可以求解出序列 X 和 Y 的最长公共子序列的长度。希望这个解题思路能够帮助你理解如何使用动态规划来解决最长公共子序列问题。


🎃代码分析：

main 方法：

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String X = "ABCBDAB";
    String Y = "BDCABA";
    int[][] C = LCSLength(X, Y);
    System.out.println("最长公共子序列长度为：" + C[X.length()][Y.length()]);
    System.out.print("最长公共子序列为：");
    printLCS(C, X, Y, X.length(), Y.length());
  }


  • 在主方法中定义了两个字符串 X 和 Y，分别为 "ABCBDAB" 和 "BDCABA"。
  • 创建一个二维数组 C，并调用 LCSLength 方法计算最长公共子序列的长度，并将结果存储在数组 C 中。
  • 打印最长公共子序列的长度。
  • 调用 printLCS 方法，传入数组 C、字符串 X、字符串 Y 以及字符串 X 和 Y 的长度，打印最长公共子序列。


LCSLength 方法：

  public static int[][] LCSLength(String X, String Y) {
    int m = X.length();
    int n = Y.length();
    int[][] C = new int[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
      C[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
      C[0][j] = 0;
    }
 
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
          C[i][j] = C[i - 1][j - 1] + 1;
        } else {
          C[i][j] = Math.max(C[i - 1][j], C[i][j - 1]);
        }
      }
    }
 
    return C;
  }


  • 此方法用于计算给定两个字符串 X 和 Y 的最长公共子序列的长度。
  • 首先获取字符串 X 和 Y 的长度并创建一个大小为 (m+1) x (n+1) 的二维数组 C，其中 m 和 n 分别是字符串 X 和 Y 的长度。
  • 初始化数组 C 的第一行和第一列为 0。
  • 使用两个嵌套的 for 循环遍历字符串 X 和 Y 的所有组合。
  • 如果 X.charAt(i-1) 等于 Y.charAt(j-1)，则说明当前字符属于最长公共子序列，此时将 C[i][j] 设置为 C[i-1][j-1] + 1。
  • 否则，根据动态规划的规则选择 C[i-1][j] 和 C[i][j-1] 中的较大值赋给 C[i][j]。
  • 最后返回填充好的数组 C。

printLCS 方法：

  public static void printLCS(int[][] C, String X, String Y, int i, int j) {
    if (i == 0 || j == 0) {
      return;
    }
    if (X.charAt(i - 1) == Y.charAt(j - 1)) {
      printLCS(C, X, Y, i - 1, j - 1);
      System.out.print(X.charAt(i - 1));
    } else if (C[i - 1][j] >= C[i][j - 1]) {
      printLCS(C, X, Y, i - 1, j);
    } else {
      printLCS(C, X, Y, i, j - 1);
    }
  }


  • 此方法用于回溯求解最长公共子序列，并将其打印出来。
  • 如果 i 或 j 为 0，则表示已经回溯到了边界，直接返回。
  • 如果 X.charAt(i-1) 等于 Y.charAt(j-1)，则说明当前字符属于最长公共子序列，递归调用 printLCS 方法继续向前找，并打印当前字符。
  • 否则，根据动态规划的规则，如果 C[i-1][j] 大于等于 C[i][j-1]，则递归调用 printLCS 方法向上找；否则，递归调用 printLCS 方法向左找。


🎃总代码：

package one;
 
public class Sameple {
 
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    String X = "ABCBDAB";
    String Y = "BDCABA";
    int[][] C = LCSLength(X, Y);
    System.out.println("最长公共子序列长度为：" + C[X.length()][Y.length()]);
    System.out.print("最长公共子序列为：");
    printLCS(C, X, Y, X.length(), Y.length());
  }
 
  public static int[][] LCSLength(String X, String Y) {
    int m = X.length();
    int n = Y.length();
    int[][] C = new int[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
      C[i][0] = 0;
    }
    for (int j = 0; j <= n; j++) {
      C[0][j] = 0;
    }
 
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (X.charAt(i - 1) == Y.charAt(j - 1)) {
          C[i][j] = C[i - 1][j - 1] + 1;
        } else {
          C[i][j] = Math.max(C[i - 1][j], C[i][j - 1]);
        }
      }
    }
 
    return C;
  }
 
  public static void printLCS(int[][] C, String X, String Y, int i, int j) {
    if (i == 0 || j == 0) {
      return;
    }
    if (X.charAt(i - 1) == Y.charAt(j - 1)) {
      printLCS(C, X, Y, i - 1, j - 1);
      System.out.print(X.charAt(i - 1));
    } else if (C[i - 1][j] >= C[i][j - 1]) {
      printLCS(C, X, Y, i - 1, j);
    } else {
      printLCS(C, X, Y, i, j - 1);
    }
  }
}

🎃运行截图：

🎯 做题方法总结：

动态规划（Dynamic Programming）是一种通过将问题划分为子问题并为子问题找到最优解来解决复杂问题的算法思想。它通常用于解决具有重叠子问题和最优子结构性质的问题。


以下是使用动态规划解决问题的一般步骤：


  1. 定义子问题： 确定问题可以被划分为若干个子问题。这些子问题通常与原问题相似，但规模较小。
  2. 建立状态转移方程： 定义问题的状态以及状态之间的关系。通过求解子问题，可以推导出原问题的解。
  3. 确定初始条件： 确定最小子问题的解，作为递归或迭代的起点。
  4. 填充表格或数组： 使用循环结构计算并填充数组或表格，以解决子问题。通常从最小子问题开始，逐步计算到原问题。
  5. 返回结果： 根据问题的要求，从填充的表格或数组中得出最终的结果。


下面是一个更具体的动态规划法解题的示例：


  1. 问题定义： 定义问题的具体要求。例如，求解最长公共子序列、最优路径、最大值等。
  2. 状态定义： 定义问题的状态。确定需要记录的信息，以及如何表示状态。
  3. 状态转移方程： 建立状态之间的关系。根据问题的性质和要求，确定状态之间的转移方式。
  4. 初始条件： 确定最小子问题的解，作为递归或迭代的起点。
  5. 计算顺序： 根据状态转移方程，确定计算子问题的顺序。通常从最小子问题开始，逐步计算到原问题。
  6. 填充表格或数组： 使用循环结构计算并填充数组或表格，以解决子问题。根据计算顺序，依次填充表格中的每个元素。
  7. 返回结果： 根据问题的要求，从填充的表格或数组中得出最终的结果。


需要注意的是，动态规划法适用于具有重叠子问题和最优子结构性质的问题。在实际应用中，可以根据具体问题的特点灵活运用动态规划思想，设计合适的状态和状态转移方程，以提高问题的求解效率。

文章标签：
算法
人工智能
Python
Android开发
存储
Y小夜
目录
相关文章
Y小夜
|
2月前
|
算法 机器学习/深度学习 索引
【算法设计与分析】——搜索算法
【算法设计与分析】——搜索算法
Y小夜
40 1
TJUTCM-策士之九尾
|
7月前
|
算法 数据挖掘 调度
【算法分析与设计】贪心算法（下）
【算法分析与设计】贪心算法（下）
TJUTCM-策士之九尾
110 0
【算法分析与设计】贪心算法（下）
Y小夜
|
2月前
|
存储 算法 搜索推荐
【算法设计与分析】—— 分治算法
【算法设计与分析】—— 分治算法
Y小夜
25 0
Y小夜
|
2月前
|
人工智能 算法 Java
【算法设计与分析】— —单源最短路径的贪心算法
【算法设计与分析】— —单源最短路径的贪心算法
Y小夜
32 0
哥的时代
|
4月前
|
设计模式 算法 知识图谱
算法设计与分析（贪心法）
【1月更文挑战第1天】在分析问题是否具有最优子结构性质时，通常先设出问题的最优解，给出子问题的解一定是最优的结论。证明思路是：设原问题的最优解导出子问题的解不是最优的，然后在这个假设下可以构造出比原问题的最优解更好的解，从而导致矛盾。（一个问题能够分解成各个子问题来解决，通过各个子问题的最优解能递推到原问题的最优解，此时原问题的最优解一定包含各个子问题的最优解，这是能够采用贪心法来求解问题的关键）贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择获得，即通过一系列的逐步局部最优选择使得最终的选择方案是全局最优的。
哥的时代
75 1
TJUTCM-策士之九尾
|
9月前
|
算法
算法设计与分析（上）
笔记
TJUTCM-策士之九尾
68 0
TJUTCM-策士之九尾
|
7月前
|
机器学习/深度学习 存储 算法
【算法分析与设计】贪心算法（上）
【算法分析与设计】贪心算法（上）
TJUTCM-策士之九尾
63 0
TJUTCM-策士之九尾
|
9月前
|
算法
算法设计与分析（下）
笔记
TJUTCM-策士之九尾
68 0
zombo_tany
|
算法
算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）
算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）
zombo_tany
146 0
算法设计与分析/数据结构与算法实验7：0-1背包问题（分支限界法）
TiAmoZhang
|
存储 算法
秒懂算法 | 动态规划算法的基本思想
介绍动态规划的思想。
TiAmoZhang
186 0
秒懂算法 | 动态规划算法的基本思想

热门文章

最新文章

  • 1
    解决关于Windows Defender Antivirus Service自启造成运行python程序时，Windows的cpu和内存占用过高问题
  • 2
    订票系统不再瘫痪 阿里云确认与12306合作
  • 3
    iOS - 手动下架的应用后快速恢复上架
  • 4
    du 和 df以及lsof
  • 5
    库克：苹果不是只做富人生意，还一直坚持让世界变得更好
  • 6
    WiGig无线标准正式开始提供验证 最高可达8Gbps
  • 7
    IBM推出新的16位量子处理器
  • 8
    Android:随笔——对页面的View进行截图
  • 9
    shell MAC 地址 校验
  • 10
    【系统优化】数据库系统load飙高问题解决思路
  • 1
    DataWorks产品使用合集之DataWorks中，如果一个虚拟节点被设置为冻结状态，那么它的所有子节点也将被冻结如何解决
    24
  • 2
    DataWorks产品使用合集之DataWorks发布任务的方法如何解决
    25
  • 3
    DataWorks产品使用合集之DataWorks中，配置DataHub数据源如何解决
    23
  • 4
    Nacos 1.4.1核心功能组件及使用入门
    22
  • 5
    DataWorks产品使用合集之在 DataWorks 中，有一个 MySQL 数据表，数据量非常大且数据会不断更新将这些数据同步到 DataWorks如何解决
    14
  • 6
    基于直方图的图像阈值计算和分割算法FPGA实现,包含tb测试文件和MATLAB辅助验证
    14
  • 7
    DataWorks产品使用合集之在DataWorks中，要实现MySQL数据源的增量同步如何解决
    17

    • 相关课程

    更多
  • 【算法实战】10. 树回归算法
  • 【算法实战】2. K近邻算法
  • 【算法实战】5. Logistic回归算法
  • 【算法实战】12. 利用 Apriori 算法进行关联分析
  • 【算法实战】9. 线性回归算法
  • 【算法实战】4. 朴素贝叶斯算法

    • 相关电子书

    更多
  • 考察数据科学家支持向量机（SVM）知识的25道题，快来测测吧
  • 图解算法小抄
  • 概率图模型

    • 相关实验场景

    更多
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考