算法：01背包和完全背包问题
算法：01背包和完全背包问题
一、题目
背包问题指的是给定2个数组，分别表示一组物品的容量和价值。给定一个背包容量。问在不超过背包容量的前提下能装的物品的最大价值。
背包问题细分有：
- 01背包问题
- 完全背包问题
- 多重背包问题
- 其他组合背包问题
主要区分在放入物品的数量的限制上。比如01背包问题只能放或者不放1个；完全背包不限制数量；多重背包限制指定数量等。
实际面试场景中都是背包问题的变种，考察的是掌握背包问题在实际场景中的灵活运用。
本文主要介绍01背包问题和完全背包问题。
二、输入
- 两个相同大小的数组。数组长度对应物品的数量，数组分别对应物品的容量和价值。
- 待放入物品的背包总容量
- 物品的数量（可选）
注意物品的容量有的地方也理解为重量，两者可以互换
注意物品的容量有的地方也理解为重量，两者可以互换
三、输出
装入物品的最大价值
四、示例
1 | 输入：int[] w = new int[]{1, 3, 4}; //物品重量int[] v = new int[]{15, 20, 30};// 物品价值int n = 3; // 物品数int c = 4; // 背包容量输出：35 |
1 | 输入：int[] w = new int[]{1, 3, 4}; //物品重量int[] v = new int[]{15, 20, 30};// 物品价值int n = 3; // 物品数int c = 4; // 背包容量输出：35 |
五、题解
- 背包问题大家都知道是动态规划的经典案例。动态规划本质是从遍历所有解找最优子结构，重复子问题降低复杂度。动态规划解答前最好了解暴搜遍历的方法。对应这里的是回溯算法（选还是不选）
- 动态规划解法先从2维动态数组理解，再考虑一维滚动数组的优化
- dp[i][j]表示从0~i件物品中选择，背包容量不超过j时背包的最大价值
- dp[j]表示背包容量不超过j时背包的最大价值
- 01背包和完全背包的转移方程有小的差别，原因是完全背包中同一个物品可以多次选择。 01背包：dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]； 完全背包：dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i]
- 二维动态数组优化为一维数组时需要注意遍历的顺序。01背包问题需要从背包容量最大值到最小值，避免同一件物品被重复计算（放入包中）。二维动态数组没有这个问题，因为第i-1个物品对应的dp值已经被固化，不会被覆盖了
- 背包问题2层循环一般外层遍历物品，内层遍历背包容量。对于2维动态数组2层循环遍历顺序影响不大；对于1维动态数组解决01背包问题要求外层先遍历物品
1 | dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w[i]] + v[i] |
1 | dp[i][j] = Math.max(dp[i-1][j], dp[i][j-w[i]] + v[i] |
5.1 01背包 Java 实现
1 | package org.stone.study.algo.dp;/** * 01背包问题 */public class Knapsack_01_Problem { public static void main(String[] args) {/* int[] w = {2, 2, 6, 5, 4}; int[] v = {6, 3, 5, 4, 6}; int c = 10;*/ int[] w = {1, 3, 4}; int[] v = {15, 20, 30}; int c = 4; // 15 // 35 System.out.println(knapsack_01(w, v, c)); } /** * 0/1背包问题：暴力解法和动态规划解法 */ public static int knapsack_01(int[] w, int[] v, int c) { // 暴力回溯解法 // return backtrack(w, v, c, 0); // 动态规划解法：二维dp数组 // return dp_01(w, v, c); // 动态规划解法：一维dp数组 return dp_01_rolling_array(w, v, c); } /** * 0/1背包问题：动态规划解法 - 二维dp数组 */ private static int dp_01(int[] w, int[] v, int c) { int n = w.length; // 定义dp数组，dp[i][j]表示前i个物品，背包容量为j时（不超过j）的最大价值 int[][] dp = new int[n][c+1]; // 初始化：背包容量不足w[0]时，价值为0 for(int j = w[0]; j <= c; j++) { dp[0][j] = v[0]; } // 先遍历物品，再遍历容量 for(int i = 1; i < n; i++) { for (int j = 1; j <= c; j++) { // 可以放入当前物品 if (j - w[i] >= 0) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } else { // 不能放入当前物品 dp[i][j] = dp[i - 1][j]; } } } return dp[n-1][c]; } /** * 0/1背包问题：动态规划解法 - 一维dp数组（滚动数组）- 从后往前遍历 * @param w * @param v * @param c * @return */ private static int dp_01_rolling_array(int[] w, int[] v, int c) { int n = w.length; int[] dp = new int[c+1]; for(int i = 0; i < n; i++) { // 容量从后往前遍历，避免使用dp数组前值（同一个背包使用多次， 0/1背包要求只能使用一次） for(int j = c; j >= w[i]; j--) { dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]); } } return dp[c]; } /** * 暴力解法，回溯算法：选或者不选 * @param w 物品重量 * @param v 物品价值 * @param leftCapacity 背包剩余容量 * @param idx 当前物品索引 * @return */ private static int backtrack(int[] w, int[] v, int leftCapacity, int idx) { // 递归终止条件 if (idx == w.length || leftCapacity <= 0) { return 0; } // 不选当前物品 int exclusive = backtrack(w, v, leftCapacity, idx + 1); // 选当前物品 int inclusive = 0; if (w[idx] <= leftCapacity) { inclusive = backtrack(w, v, leftCapacity - w[idx], idx + 1) + v[idx]; } // 取最大值 return Math.max(exclusive, inclusive); }} |
1 | package org.stone.study.algo.dp;/** * 01背包问题 */public class Knapsack_01_Problem { public static void main(String[] args) {/* int[] w = {2, 2, 6, 5, 4}; int[] v = {6, 3, 5, 4, 6}; int c = 10;*/ int[] w = {1, 3, 4}; int[] v = {15, 20, 30}; int c = 4; // 15 // 35 System.out.println(knapsack_01(w, v, c)); } /** * 0/1背包问题：暴力解法和动态规划解法 */ public static int knapsack_01(int[] w, int[] v, int c) { // 暴力回溯解法 // return backtrack(w, v, c, 0); // 动态规划解法：二维dp数组 // return dp_01(w, v, c); // 动态规划解法：一维dp数组 return dp_01_rolling_array(w, v, c); } /** * 0/1背包问题：动态规划解法 - 二维dp数组 */ private static int dp_01(int[] w, int[] v, int c) { int n = w.length; // 定义dp数组，dp[i][j]表示前i个物品，背包容量为j时（不超过j）的最大价值 int[][] dp = new int[n][c+1]; // 初始化：背包容量不足w[0]时，价值为0 for(int j = w[0]; j <= c; j++) { dp[0][j] = v[0]; } // 先遍历物品，再遍历容量 for(int i = 1; i < n; i++) { for (int j = 1; j <= c; j++) { // 可以放入当前物品 if (j - w[i] >= 0) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]); } else { // 不能放入当前物品 dp[i][j] = dp[i - 1][j]; } } } return dp[n-1][c]; } /** * 0/1背包问题：动态规划解法 - 一维dp数组（滚动数组）- 从后往前遍历 * @param w * @param v * @param c * @return */ private static int dp_01_rolling_array(int[] w, int[] v, int c) { int n = w.length; int[] dp = new int[c+1]; for(int i = 0; i < n; i++) { // 容量从后往前遍历，避免使用dp数组前值（同一个背包使用多次， 0/1背包要求只能使用一次） for(int j = c; j >= w[i]; j--) { dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]); } } return dp[c]; } /** * 暴力解法，回溯算法：选或者不选 * @param w 物品重量 * @param v 物品价值 * @param leftCapacity 背包剩余容量 * @param idx 当前物品索引 * @return */ private static int backtrack(int[] w, int[] v, int leftCapacity, int idx) { // 递归终止条件 if (idx == w.length || leftCapacity <= 0) { return 0; } // 不选当前物品 int exclusive = backtrack(w, v, leftCapacity, idx + 1); // 选当前物品 int inclusive = 0; if (w[idx] <= leftCapacity) { inclusive = backtrack(w, v, leftCapacity - w[idx], idx + 1) + v[idx]; } // 取最大值 return Math.max(exclusive, inclusive); }} |
5.2 完全背包 Java 实现
1 | package org.stone.study.algo.dp;/** * 完全背包问题 */public class Knapsack_Complete_Problem { public static void main(String[] args) {/* int n = 5, w = 10; int[] weights = new int[]{2, 2, 6, 5, 4}; int[] vals = new int[]{6, 3, 5, 4, 6};*/ int n = 3, w = 4; int[] weights = new int[]{1, 3, 4}; int[] vals = new int[]{15, 20, 30}; int ans = complete_bag_02(n, w, weights, vals); // 第1组测试数据：30 // 第2组测试数据：60 System.out.println("bag total value:" + ans); } /** * 完全背包问题（物品可以使用多次） - 使用暴力解法回溯算法实现 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_01(int n, int w, int[] weights, int[] vals) { return backtrack(0, w, weights, vals); } /** * 完全背包问题（物品可以使用多次） - 回溯解法 * @param i * @param w * @param weights * @param vals * @return */ public static int backtrack(int i, int w, int[] weights, int[] vals) { if (i == weights.length || w <= 0) { return 0; } // 不选择当前物品 int maxValue = backtrack(i + 1, w, weights, vals); // 选择当前物品: 可多件 for (int j = 0; j * weights[i] <= w; j++) { maxValue = Math.max(maxValue, backtrack(i + 1, w - j * weights[i], weights, vals) + j * vals[i]); } return maxValue; } /** * 完全背包问题（物品可以使用多次） - 动态规划 2维 数组解法 - 先遍历物品，再遍历重量 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_02(int n, int w, int[] weights, int[] vals) { // dp[i][j]表示前i个物品，背包容量为j时的最大价值 int[][] dp = new int[n][w+1]; // 先遍历物品，再遍历重量 for(int i = 0; i < n; i++) { for (int j = weights[i]; j <= w; j++) { // 不放物品i if ( i > 0) { dp[i][j] = dp[i-1][j]; } // 放物品i // 注意对于完全背包问题：dp[i][j]是从dp[i][j]和dp[i][j-weights[i]]中推导出来的 dp[i][j] = Math.max(dp[i][j], dp[i][j - weights[i]] + vals[i]); } } return dp[n-1][w]; } /** * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历物品，再遍历重量 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_03(int n, int w, int[] weights, int[] vals) { // dp[j]表示背包容量为j时的最大价值 int[] dp = new int[w+1]; // 先遍历物品，再遍历重量 for(int i = 0; i < n; i++) { // 注意：这里是从小到大遍历。因为物品可以使用多次。dp[j]可以依赖dp[j-weights[i]] for (int j = weights[i]; j <= w; j++) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]); } } return dp[w]; } /** * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历重量，再遍历物品 * @param n * @param w * @param weights * @param vals * @return */ private static int complete_bag_04(int n, int w, int[] weights, int[] vals) { int[] dp = new int[w + 1]; // 先遍历重量，再遍历物品 for (int j = 1; j <= w; j++) { for (int i = 0; i < n; i++) { if (j - weights[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]); } } } return dp[w]; }} |
1 | package org.stone.study.algo.dp;/** * 完全背包问题 */public class Knapsack_Complete_Problem { public static void main(String[] args) {/* int n = 5, w = 10; int[] weights = new int[]{2, 2, 6, 5, 4}; int[] vals = new int[]{6, 3, 5, 4, 6};*/ int n = 3, w = 4; int[] weights = new int[]{1, 3, 4}; int[] vals = new int[]{15, 20, 30}; int ans = complete_bag_02(n, w, weights, vals); // 第1组测试数据：30 // 第2组测试数据：60 System.out.println("bag total value:" + ans); } /** * 完全背包问题（物品可以使用多次） - 使用暴力解法回溯算法实现 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_01(int n, int w, int[] weights, int[] vals) { return backtrack(0, w, weights, vals); } /** * 完全背包问题（物品可以使用多次） - 回溯解法 * @param i * @param w * @param weights * @param vals * @return */ public static int backtrack(int i, int w, int[] weights, int[] vals) { if (i == weights.length || w <= 0) { return 0; } // 不选择当前物品 int maxValue = backtrack(i + 1, w, weights, vals); // 选择当前物品: 可多件 for (int j = 0; j * weights[i] <= w; j++) { maxValue = Math.max(maxValue, backtrack(i + 1, w - j * weights[i], weights, vals) + j * vals[i]); } return maxValue; } /** * 完全背包问题（物品可以使用多次） - 动态规划 2维 数组解法 - 先遍历物品，再遍历重量 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_02(int n, int w, int[] weights, int[] vals) { // dp[i][j]表示前i个物品，背包容量为j时的最大价值 int[][] dp = new int[n][w+1]; // 先遍历物品，再遍历重量 for(int i = 0; i < n; i++) { for (int j = weights[i]; j <= w; j++) { // 不放物品i if ( i > 0) { dp[i][j] = dp[i-1][j]; } // 放物品i // 注意对于完全背包问题：dp[i][j]是从dp[i][j]和dp[i][j-weights[i]]中推导出来的 dp[i][j] = Math.max(dp[i][j], dp[i][j - weights[i]] + vals[i]); } } return dp[n-1][w]; } /** * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历物品，再遍历重量 * @param n * @param w * @param weights * @param vals * @return */ public static int complete_bag_03(int n, int w, int[] weights, int[] vals) { // dp[j]表示背包容量为j时的最大价值 int[] dp = new int[w+1]; // 先遍历物品，再遍历重量 for(int i = 0; i < n; i++) { // 注意：这里是从小到大遍历。因为物品可以使用多次。dp[j]可以依赖dp[j-weights[i]] for (int j = weights[i]; j <= w; j++) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]); } } return dp[w]; } /** * 完全背包问题（物品可以使用多次） - 动态规划滚动数组解法 - 先遍历重量，再遍历物品 * @param n * @param w * @param weights * @param vals * @return */ private static int complete_bag_04(int n, int w, int[] weights, int[] vals) { int[] dp = new int[w + 1]; // 先遍历重量，再遍历物品 for (int j = 1; j <= w; j++) { for (int i = 0; i < n; i++) { if (j - weights[i] >= 0) { dp[j] = Math.max(dp[j], dp[j - weights[i]] + vals[i]); } } } return dp[w]; }} |
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 石头记！
相关推荐
2024-12-02
算法：N 皇后问题
算法：N 皇后问题一、题目按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。 每一种解法包含一个不同的 n...
2026-02-11
RocketMQ不能消费消息问题调查
RocketMQ不能消费消息问题调查一、问题最近一个Spring Cloud微服务项目中定义的RocketMQ Consumer Bean不能正常触发消息消费。问题发生在测试环境。 这个功能以前是好的，生产环境和预发环境也是正常的。 二、定位RocketMQ是阿里开源的用Java实现的消息中间...
2024-11-05
算法：数组去重并排序
算法：数组去重并排序一、题目1题目：给定一个乱序的数组，删除所有的重复元素，使得每个元素只出现一次，并且按照出现的次数从高到低进行排序，相同出现次数按照第一次出现顺序进行先后排序。备注: 数组大小不超过100 数组元素值大小不超过100。输入：一个数组输出：去重排序后的数组示例：输入：1,3,...
2019-11-20
Java String intern
Java String intern11 背景Java String intern经常出现在面试题中，测试两个字符串是不是同一个对象。对于什么时候会在常量池存储字符串对象，我想我们可以基本得出结论:显示调用String的intern方法直接声明字符串字面常量的时候，例如: String a =...
2024-03-25
算法：扫描线技巧解决会议室安排问题
算法：扫描线技巧解决会议室安排问题LeetCode题目算法分析大厂面试，一道非常经典且实用的算法题目：会议室安排问题。 先说下题目，力扣第 253 题「会议室 II」（力扣上该题是会员题目，你可能没办法做）：给你输入若干形如 [begin, end] 的区间，代表若干会议的开始时间和结束时间，...
2025-12-01
Mybatis Log Free IDEA插件Bug修复
Mybatis Log Free IDEA插件Bug修复一、问题项目中一直使用Mybatis，通过Mybatis Log Free[1]插件打印执行的SQL语句，再抓出来执行或者检查逻辑，一直还挺好用的。 最近遇到一个问题，就是SQL参数值中如果包含了括号，生成的SQL语句参数替换后字符串外面...