建筑行业网站开发,重庆建筑工程网站,html5做音乐网站,手机seo关键词优化文章目录 概述背包问题01背包问题#xff1a;代码示例部分背包代码示例 完全背包代码示例 多重背包代码示例 总结提升 概述
动态规划#xff08;Dynamic Programming#xff09;是一种通过将问题划分为相互重叠的子问题来解决问题的算法思想。其核心思想是通过保存已经计算… 文章目录 概述背包问题01背包问题代码示例部分背包代码示例 完全背包代码示例 多重背包代码示例 总结提升 概述
动态规划Dynamic Programming是一种通过将问题划分为相互重叠的子问题来解决问题的算法思想。其核心思想是通过保存已经计算过的子问题的解避免重复计算从而降低时间复杂度。
动态规划的适用条件包括
问题具有最优子结构问题的最优解可以通过子问题的最优解来构造。 子问题之间存在重叠原问题的求解过程中多次求解相同的子问题。 动态规划的基本步骤如下
1、定义状态明确问题的状态并用状态变量表示。 2、确定状态转移方程根据问题的最优子结构确定状态之间的转移关系。 3、初始化设置初始状态的值。 4、递推计算根据状态转移方程从初始状态逐步计算到目标状态。 5、求解目标根据最终状态的值得到问题的解。
背包问题
背包问题是一个经典的组合优化问题在计算机科学和运筹学中具有广泛的应用。它的基本形式是给定一个固定大小的背包和一组物品每个物品有对应的重量和价值。目标是在不超过背包容量的前提下选择合适的物品放入背包使得背包中物品的总价值最大化。
背包问题可以分为多个不同的变体其中最常见的有01背包问题、部分背包、完全背包问题和多重背包问题。
01背包问题
每个物品要么放入背包要么不放入背包不能拆分。 对于每个物品只有两种选择放入或者不放入背包。
代码示例
public class Knapsack {public static int knapsack(int[] weights, int[] values, int capacity) {int n weights.length; // 物品个数int[][] dp new int[n 1][capacity 1]; // 创建动态规划表for (int i 1; i n; i) {for (int j 1; j capacity; j) {if (weights[i - 1] j) {dp[i][j] dp[i - 1][j];} else {dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] values[i - 1]);}}}return dp[n][capacity];}public static void main(String[] args) {int[] weights {2, 3, 4, 5}; // 物品重量int[] values {3, 4, 5, 6}; // 物品价值int capacity 8; // 背包容量int max_value knapsack(weights, values, capacity);System.out.println(最大价值: max_value);}
}
这段代码实现了 01 背包问题的动态规划解法。knapsack 方法接受物品重量数组 weights、物品价值数组 values 和背包容量 capacity 作为输入并返回最大的背包价值。
代码中创建了一个二维数组 dp 来存储子问题的最优解。通过两层循环遍历每个子问题并根据状态转移方程更新 dp 数组。最后返回 dp[n][capacity]即表示最大的背包价值。
在上述示例中测试样例中的物品重量为 [2, 3, 4, 5]物品价值为 [3, 4, 5, 6]背包容量为 8。输出结果为最大价值为 11。
部分背包
部分背包问题是一个在给定背包容量的限制下选择物品放入背包以使得背包的总价值最大化的问题。与 0-1 背包问题不同的是部分背包问题允许将物品分割成小块并且可以选择装入一部分物品。
在部分背包问题中每个物品都有一个重量和一个价值。目标是选择一些物品装入背包使得被选中物品的总重量不超过背包的容量同时使得它们的总价值最大化。
为了解决这个问题我们可以根据物品的单位价值即每单位重量的价值进行排序然后按照从高到低的顺序依次装入物品直到背包无法再装入完整的物品为止。如果背包仍有剩余容量则根据物品的单位价值将其分割成部分并将部分装入背包使得装入的部分物品价值最大化。
部分背包问题可以使用贪心算法来求解。通过按照单位价值排序并可根据限制条件逐步装入物品贪心算法能够在较短的时间内得到一个近似最优解。
需要注意的是部分背包问题的贪心算法并不一定能够得到最优解。在某些情况下贪心选择可能会导致次优解或者错误的结果。因此对于严格要求最优解的问题可能需要使用其他算法来求解如动态规划等。
代码示例
public class FractionalKnapsack {public static double fractionalKnapsack(int[] weights, int[] values, int capacity) {int n weights.length;double[][] dp new double[n 1][capacity 1];for (int i 1; i n; i) {int weight weights[i - 1];int value values[i - 1];for (int j 1; j capacity; j) {if (weight j) {// 可以完整装入当前物品dp[i][j] Math.max(dp[i - 1][j], dp[i - 1][j - weight] value);} else {// 只能装入一部分当前物品dp[i][j] dp[i - 1][j];}}}return dp[n][capacity];}public static void main(String[] args) {int[] weights {2, 3, 4, 5};int[] values {3, 4, 5, 6};int capacity 8;double max_value fractionalKnapsack(weights, values, capacity);System.out.println(最大总价值: max_value);}
}
这段代码使用动态规划算法解决部分背包问题。weights 数组存储物品的重量values 数组存储物品的价值capacity 表示背包的容量。
通过创建一个二维数组 dp其中 dp[i][j] 表示在考虑前 i 个物品并且背包容量为 j 时的最大总价值。
代码中使用两层循环遍历所有物品和背包容量的组合。对于每个物品分为两种情况进行处理
如果当前物品的重量小于等于背包容量可以选择完整装入该物品。此时最大总价值等于不装入该物品时的最大总价值 dp[i-1][j] 和装入该物品后的总价值 dp[i-1][j-weight] value 中的较大值。 如果当前物品的重量大于背包容量无法完整装入该物品。此时最大总价值与上一个物品时的价值相同即 dp[i][j] dp[i-1][j]。 最后返回二维数组 dp 中最后一个元素的值即表示在考虑所有物品时背包可以装入的最大总价值。
在上述示例中测试样例中的物品数组包含四个物品每个物品的重量和价值分别为 2、3、4、5 和 3、4、5、6背包容量为 8。输出结果为最大总价值为 11.0。
完全背包
完全背包问题是一个在给定背包容量的限制下选择物品放入背包以使得背包的总价值最大化的问题。与 0-1 背包问题和部分背包问题不同的是完全背包问题允许将物品无限次地装入背包中。
在完全背包问题中每个物品都有一个重量和一个价值。与部分背包问题类似目标是选择一些物品装入背包使得被选中物品的总重量不超过背包的容量同时使得它们的总价值最大化。
为了解决这个问题我们可以使用动态规划算法。通过创建一个二维数组 dp其中 dp[i][j] 表示在考虑前 i 个物品并且背包容量为 j 时的最大总价值。
与部分背包问题不同的是在完全背包问题中对于每个物品我们可以选择装入 0 个、1 个、2 个… 直到 j/weight[i] 个j/weight[i] 向下取整个物品。
因此对于每个物品 i我们可以使用以下递推关系来计算 dp[i][j]
dp[i][j] max(dp[i-1][j-k*weight[i]] k*value[i])其中 0 k j/weight[i]
遍历所有物品和背包容量的组合通过上述递推关系更新 dp 数组中的值。
最后返回二维数组 dp 中最后一个元素的值即表示在考虑所有物品时背包可以装入的最大总价值。
需要注意的是完全背包问题的动态规划解法时间复杂度较高并且可能需要大量的内存空间。为了提高效率我们可以使用一维数组进行优化在遍历物品时从小到大的顺序更新 dp 数组。
代码示例
public class CompleteKnapsack {public static int completeKnapsack(int[] weights, int[] values, int capacity) {int n weights.length;int[] dp new int[capacity 1];for (int i 0; i n; i) {int weight weights[i];int value values[i];for (int j weight; j capacity; j) {dp[j] Math.max(dp[j], dp[j - weight] value);}}return dp[capacity];}public static void main(String[] args) {int[] weights {2, 3, 4, 5};int[] values {3, 4, 5, 6};int capacity 8;int max_value completeKnapsack(weights, values, capacity);System.out.println(最大总价值: max_value);}
}
这段代码使用动态规划算法解决完全背包问题。weights 数组存储物品的重量values 数组存储物品的价值capacity 表示背包的容量。
通过创建一个一维数组 dp其中 dp[j] 表示在考虑前所有物品并且背包容量为 j 时的最大总价值。
代码中首先遍历所有物品然后遍历所有可能的容量对于每个容量 j计算出背包可以装入的最大总价值。
递推公式为
dp[j] max(dp[j], dp[j - weight] value)其中weights[i] 表示第 i 个物品的重量values[i] 表示第 i 个物品的价值。
在更新 dp[j] 的值时我们将 dp[j-weight]value 的值与 dp[j] 的值比较取两者中的最大值作为新的 dp[j] 值。
最后返回一维数组 dp 中最后一个元素的值即表示在考虑所有物品时背包可以装入的最大总价值。
在上述示例中测试样例中的物品数组包含四个物品每个物品的重量和价值分别为 2、3、4、5 和 3、4、5、6背包容量为 8。输出结果为最大总价值为 18。
多重背包
多重背包问题是在给定背包容量的限制下选择物品放入背包以使得背包的总价值最大化的问题。与完全背包问题类似多重背包问题允许将某些物品选择多次放入背包中但是每个物品的选择次数是有限制的。
在多重背包问题中每个物品都有一个重量、价值和一个数量限制。目标是选择一些物品放入背包使得被选中物品的总重量不超过背包的容量同时使得它们的总价值最大化。
为了解决多重背包问题我们可以使用动态规划算法。通过创建一个二维数组 dp其中 dp[i][j] 表示在考虑前 i 个物品并且背包容量为 j 时的最大总价值。
与完全背包问题类似对于每个物品 i我们需要考虑选择物品 i 的次数。假设该物品的选择次数上限为 k则选择次数的范围是 0 到 min(k, j/weight[i])。
因此对于每个物品 i我们可以使用以下递推关系来计算 dp[i][j]
dp[i][j] max(dp[i-1][j-k*weight[i]] k*value[i])其中 0 k min(k, j/weight[i])遍历所有物品和背包容量的组合通过上述递推关系更新 dp 数组中的值。
最后返回二维数组 dp 中最后一个元素的值即表示在考虑所有物品时背包可以装入的最大总价值。
需要注意的是多重背包问题的动态规划解法时间复杂度较高并且可能需要大量的内存空间。为了提高效率我们可以使用一维数组进行优化在遍历物品时从大到小的顺序更新 dp 数组。
代码示例
public class MultipleKnapsack {public static int multipleKnapsack(int[] weights, int[] values, int[] counts, int capacity) {int n weights.length;int[] dp new int[capacity 1];for (int i 0; i n; i) {int weight weights[i];int value values[i];int count counts[i];for (int j capacity; j weight; j--) {for (int k 1; k count k * weight j; k) {dp[j] Math.max(dp[j], dp[j - k * weight] k * value);}}}return dp[capacity];}public static void main(String[] args) {int[] weights {2, 3, 4};int[] values {3, 4, 5};int[] counts {2, 3, 1};int capacity 8;int max_value multipleKnapsack(weights, values, counts, capacity);System.out.println(最大总价值: max_value);}
}
这段代码使用动态规划算法解决多重背包问题。weights 数组存储物品的重量values 数组存储物品的价值counts 数组存储每个物品的数量限制capacity 表示背包的容量。
通过创建一个一维数组 dp其中 dp[j] 表示在考虑前所有物品并且背包容量为 j 时的最大总价值。
代码中首先遍历所有物品然后通过两层循环遍历背包容量和物品的选择次数。对于每个物品计算出选择不同次数情况下的最大总价值。
递推公式为
dp[j] max(dp[j], dp[j-k*weight]k*value)其中 1 k min(count, j/weight)
在更新 dp[j] 的值时我们将 dp[j-kweight]kvalue 的值与 dp[j] 的值比较取两者中的最大值作为新的 dp[j] 值。
最后返回一维数组 dp 中最后一个元素的值即表示在考虑所有物品时背包可以装入的最大总价值。
在上述示例中测试样例中的物品数组包含三个物品每个物品的重量和价值分别为 2、3、4 和 3、4、5数量限制分别为 2、3、1背包容量为 8。输出结果为最大总价值为 20。
总结提升
