杭州制作网站公司,网站建设出找不到网页,平面设计好学吗?没有基础,哪里做网站最便宜#x1f383;个人专栏#xff1a; #x1f42c; 算法设计与分析#xff1a;算法设计与分析_IT闫的博客-CSDN博客 #x1f433;Java基础#xff1a;Java基础_IT闫的博客-CSDN博客 #x1f40b;c语言#xff1a;c语言_IT闫的博客-CSDN博客 #x1f41f;MySQL#xff1a… 个人专栏 算法设计与分析算法设计与分析_IT闫的博客-CSDN博客 Java基础Java基础_IT闫的博客-CSDN博客 c语言c语言_IT闫的博客-CSDN博客 MySQL数据结构_IT闫的博客-CSDN博客 数据结构数据结构_IT闫的博客-CSDN博客 CC_IT闫的博客-CSDN博客 C51单片机C51单片机STC89C516_IT闫的博客-CSDN博客 基于HTML5的网页设计及应用基于HTML5的网页设计及应用_IT闫的博客-CSDN博客 pythonpython_IT闫的博客-CSDN博客 离散数学离散数学_IT闫的博客-CSDN博客 欢迎收看希望对大家有用 目录
内容概括
目的
基本步骤
环境
内容
one
问题
解题思路
代码分析
总代码 运行截图 two
问题
解题思路
代码分析
总代码
运行截图 three
问题
解题思路
代码分析 总代码 做题方法总结 内容概括 1矩阵连乘问题已知矩阵A1A2A3A4A5 使用向量PP03P12P25P310P42P53存储行列求出相乘次数最少的加括号位置。 20-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 使用向量PP03P12P25P310P42P53存储行列求出相乘次数最少的加括号位置。 解题思路 创建两个二维数组m和s其中m[i][j]表示从矩阵Ai到Aj的连乘所需的最少次数s[i][j]表示从矩阵Ai到Aj的连乘的最优加括号位置。初始化m[i][i]为0表示单个矩阵相乘的次数为0。对于长度l2到n的子链长度依次计算m[i][j]和s[i][j] 遍历每个可能的分割点k计算m[i][j]的值。m[i][j]的值等于m[i][k] m[k1][j] Pi-1 * Pk * Pj。更新m[i][j]时同时更新s[i][j]为k表示在Ai到Aj之间最优的加括号位置是在矩阵Ak与Ak1之间。 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 (i1));} 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
问题 20-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 ≤ 50 ≤ j ≤ 10都设置为0。 接下来通过两层循环遍历物品和背包容量。外层循环表示当前所选物品的数量从1到5内层循环表示背包容量从1到10。 在每次迭代中分为两种情况进行考虑 若当前物品重量大于当前背包容量则无法选择该物品因此 dp[i][j] 的值与 dp[i-1][j] 相等。若当前物品重量小于等于当前背包容量则需要进行选择。可以比较将该物品放入背包后的总价值与不放入该物品的总价值选择其中较大的一个。即 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 SubsequenceLCS问题是经典的动态规划问题之一。给定两个序列 X 和 Y找出它们的最长公共子序列的长度。 对于序列 X{A,B,C,B,D,A,B} 和 Y{B,D,C,A,B,A}可以采用动态规划的方法来解决最长公共子序列问题。下面是解题的思路和步骤 定义状态 创建一个二维数组 dp其中 dp[i][j] 表示序列 X 的前 i 个元素与序列 Y 的前 j 个元素的最长公共子序列的长度。 状态转移方程 根据动态规划的性质我们可以使用以下状态转移方程来计算 dp[i][j] 如果 X[i-1] Y[j-1]即序列 X 的第 i-1 个元素和序列 Y 的第 j-1 个元素相等那么 dp[i][j] dp[i-1][j-1] 1表示当前这对匹配的字符可以贡献到最长公共子序列的长度中。如果 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 的最后一个元素时哪个更长。 初始化边界条件 对于 dp 数组的第一行和第一列因为其中一个序列为空时最长公共子序列的长度必定为 0所以将其初始化为 0。 填充表格 根据状态转移方程从 dp[0][0] 开始逐行或逐列填充 dp 数组直到填满整个表格。 回溯求解 最后根据填充好的 dp 数组可以进行回溯来找到具体的最长公共子序列。 通过以上步骤就可以求解出序列 X 和 Y 的最长公共子序列的长度。希望这个解题思路能够帮助你理解如何使用动态规划来解决最长公共子序列问题。 代码分析 main 方法 public static void main(String[] args) {// TODO Auto-generated method stubString 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 的长度并创建一个大小为 (m1) x (n1) 的二维数组 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 stubString 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是一种通过将问题划分为子问题并为子问题找到最优解来解决复杂问题的算法思想。它通常用于解决具有重叠子问题和最优子结构性质的问题。 以下是使用动态规划解决问题的一般步骤 定义子问题 确定问题可以被划分为若干个子问题。这些子问题通常与原问题相似但规模较小。 建立状态转移方程 定义问题的状态以及状态之间的关系。通过求解子问题可以推导出原问题的解。 确定初始条件 确定最小子问题的解作为递归或迭代的起点。 填充表格或数组 使用循环结构计算并填充数组或表格以解决子问题。通常从最小子问题开始逐步计算到原问题。 返回结果 根据问题的要求从填充的表格或数组中得出最终的结果。 下面是一个更具体的动态规划法解题的示例 问题定义 定义问题的具体要求。例如求解最长公共子序列、最优路径、最大值等。 状态定义 定义问题的状态。确定需要记录的信息以及如何表示状态。 状态转移方程 建立状态之间的关系。根据问题的性质和要求确定状态之间的转移方式。 初始条件 确定最小子问题的解作为递归或迭代的起点。 计算顺序 根据状态转移方程确定计算子问题的顺序。通常从最小子问题开始逐步计算到原问题。 填充表格或数组 使用循环结构计算并填充数组或表格以解决子问题。根据计算顺序依次填充表格中的每个元素。 返回结果 根据问题的要求从填充的表格或数组中得出最终的结果。 需要注意的是动态规划法适用于具有重叠子问题和最优子结构性质的问题。在实际应用中可以根据具体问题的特点灵活运用动态规划思想设计合适的状态和状态转移方程以提高问题的求解效率。
