龙空技术网

JAVA动态规划算法-大厂都在用

JAVA扫地僧 158

前言:

如今姐妹们对“动态规划法求解”都比较关怀,大家都想要分析一些“动态规划法求解”的相关知识。那么小编也在网络上汇集了一些对于“动态规划法求解””的相关内容,希望同学们能喜欢,我们一起来学习一下吧!

1.背包问题(Knapsack Problem)

在计算机科学中,背包问题是一类经典的组合优化问题,有多个变种。其中,最常见的是0-1背包问题和背包问题的变种:无限背包问题。这些问题都涉及在给定容量的背包中,如何选择不同重量和价值的物品,使得背包的总价值最大化。

0-1背包问题:

在0-1背包问题中,对于每种物品,你只能选择放入背包一次或不放入。每种物品有两个属性:重量(wi)和价值(vi)。背包有一个固定的容量(C),你的目标是选择一些物品放入背包,使得在不超过背包容量的情况下,背包的总价值最大化。

无限背包问题:

在无限背包问题中,对于每种物品,你可以选择放入背包的次数是无限的。每种物品仍有两个属性:重量(wi)价值(vi)。背包容量(C)仍然是固定的,你的目标是选择一些物品放入背包,使得在不超过背包容量的情况下,背包的总价值最大化。

解决这些背包问题的经典算法是动态规划。动态规划将问题划分为多个子问题,并通过解决子问题来逐步求解原始问题的最优解。

以下是0-1背包问题的动态规划解法的伪代码:

function knapsack(W, wt[], val[], n):    initialize a 2D array dp with dimensions (n+1) x (W+1) and set all values to 0        for i from 1 to n:        for w from 1 to W:            if wt[i-1] <= w:                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])            else:                dp[i][w] = dp[i-1][w]        return dp[n][W]

其中,W是背包的容量,wt[]是一个长度为n的数组,表示每种物品的重量,val[]是一个长度为n的数组,表示每种物品的价值。对于无限背包问题,只需要稍作修改即可。

请注意,以上是背包问题的动态规划解法,对于特别大的问题规模,可能需要优化和其他算法来提高效率。在实际编程中,你可以根据具体情况和需求,采用合适的算法来解决背包问题。

2.最长公共子序列(Longest Common Subsequence)

最长公共子序列(Longest Common Subsequence,简称LCS)是一个经典的字符串处理问题,在计算机科学中有广泛的应用。给定两个字符串,找出它们最长的公共子序列(可以不连续)。下面是Java中求解最长公共子序列的动态规划算法实现:

public class LongestCommonSubsequence { public static void main(String[] args) {     String str1 = "ABCDGH";     String str2 = "AEDFHR";     int result = longestCommonSubsequence(str1, str2);     System.out.println("最长公共子序列的长度为:" + result); } public static int longestCommonSubsequence(String str1, String str2) {     int m = str1.length();     int n = str2.length();     int[][] dp = new int[m + 1][n + 1];     // 填充dp数组     for (int i = 1; i <= m; i++) {         for (int j = 1; j <= n; j++) {             if (str1.charAt(i - 1) == str2.charAt(j - 1)) {                 dp[i][j] = dp[i - 1][j - 1] + 1;             } else {                 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);             }         }     }     return dp[m][n]; }}

在上面的示例中,我们计算了字符串"ABCDGH"和"AEDFHR"的最长公共子序列。程序输出为3,因为它们的最长公共子序列是"ADH"。

这里的算法使用了动态规划的思想,通过构建一个二维数组dp,其中dp[i][j]表示str1前i个字符与str2前j个字符的最长公共子序列的长度。根据字符的匹配情况,我们更新dp数组的值。最终,dp[m][n]即为最长公共子序列的长度,其中m和n分别为两个字符串的长度。

这种动态规划的解法时间复杂度为O(m*n),其中m和n分别是两个字符串的长度

3.最大子数组和(Maximum Subarray Sum)

最大子数组和(Maximum Subarray Sum)是一个经典的数组处理问题,在计算机科学中有广泛的应用。给定一个整数数组,要找到其中连续子数组的最大和。

下面是Java中求解最大子数组和的动态规划算法实现:

public class MaximumSubarraySum {    public static void main(String[] args) {        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};        int result = maxSubArray(nums);        System.out.println("最大子数组和为:" + result);    }    public static int maxSubArray(int[] nums) {        int maxSum = nums[0];        int currentSum = nums[0];        for (int i = 1; i < nums.length; i++) {            // 对于当前元素,可以选择与之前的子数组合并,或者从当前元素开始一个新的子数组            currentSum = Math.max(nums[i], currentSum + nums[i]);            maxSum = Math.max(maxSum, currentSum);        }        return maxSum;    }}

在上面的示例中,我们计算了整数数组{-2, 1, -3, 4, -1, 2, 1, -5, 4}的最大子数组和。程序输出为6,因为最大子数组是{4, -1, 2, 1},它们的和为6。

这里的算法使用了动态规划的思想,通过维护两个变量maxSum和currentSum来记录最大子数组和和当前子数组和。对于每个元素,我们可以选择将其与之前的子数组合并,或者从当前元素开始一个新的子数组。我们通过比较这两种情况的和,来更新currentSum和maxSum。

这种动态规划的解法时间复杂度为O(n),其中n是数组的长度。由于只需要遍历一次数组,所以时间复杂度是线性的。这使得这种解法非常高效。

标签: #动态规划法求解