引言
背包问题是计算机科学领域的一个经典优化问题,分为多种类型,其中最常见的是0-1背包问题和完全背包问题。这两种问题的核心在于如何在有限的空间内最大化收益,但它们之间存在一些关键的区别:0-1背包问题允许每个物品只能选择一次,而完全背包问题则允许无限次选取同一物品。本篇博客将分别介绍这两个问题的动态规划解法,并附带相应的Java代码实现。
0-1背包问题
问题描述
假设你有一个背包,其最大承重能力为W千克,现在有一系列物品,每个物品有自己的重量Wi和价值Vi。你的任务是从这些物品中挑选一部分装入背包,使得背包的价值尽可能大,但不能超过背包的最大承重限制。
解决方案
我们可以采用动态规划的方法来求解这个问题。定义一个二维数组dp[i][j]表示从前i个物品中选择若干个放入容量为j的背包所能获得的最大价值。状态转移方程
Java代码实现
package dp;import java.util.ArrayList;
import java.util.List;public class Knapsack {public static void main(String[] args) {int n = 4; // 物品数量int bagweight = 16; // 背包最大容量int[] weight = {5, 7, 3, 4}; // 物品重量int[] value = {2, 5, 8, 1}; // 物品价值// 初始化 dp 数组int[][] dp = new int[n + 1][bagweight + 1];// 动态规划填充 dp 数组for (int i = 1; i <= n; i++) {for (int j = 0; j <= bagweight; j++) {if (j < weight[i - 1]) {dp[i][j] = dp[i - 1][j]; // 不选择当前物品} else {dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println("最大价值: " + dp[n][bagweight]);// 回溯找到具体的物品List<Integer> selectedItems = new ArrayList<>();int i = n, j = bagweight;while (i > 0 && j > 0) {if (dp[i][j] != dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j -= weight[i - 1];}i--;}// 输出选择的物品System.out.print("选择的物品: ");for (int item : selectedItems) {System.out.print(item + " (重量: " + weight[item] + ", 价值: " + value[item] + ") ");}System.out.println();}
}
完全背包问题
问题描述
完全背包问题与0-1背包问题类似,不同之处在于每个物品的数量不限,即你可以无限制地选择同一个物品。
解决方案
对于完全背包问题,我们需要稍微修改一下状态转移方程。由于每个物品都可以多次选择,因此需要在循环中考虑是否要加入该物品到背包中。
-
状态表示:
- dp[i][j] 表示前 i 种物品放入容量为 j 的背包里任意取的最大价值。
-
确定边界和遍历顺序:
- 先遍历背包重量 (内层),再遍历物品 (外层循环)。
for(int i=1;i<=n;i++) // 物品数量for(int j=1;j<=m;j++) // 背包容量if(j>=w[i]) // 判断是否能放得下第i件物品dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]); // 更新dp数组else dp[i][j]=dp[i-1][j]; // 不选第i件物品
- 先遍历背包重量 (内层),再遍历物品 (外层循环)。
-
找到状态转移方程:
- 状态转移方程是关键部分,它描述了如何从已知的状态推导出新的状态。
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
- 这意味着,对于每一件物品,可以选择放进去或者不放,比较两种情况下所能获得的最大价值。
- 状态转移方程是关键部分,它描述了如何从已知的状态推导出新的状态。
Java代码实现
package dp;import java.util.ArrayList;
import java.util.List;public class AllPack {public static void main(String[] args) {int n = 3; // 物品数量int bagweight = 7; // 背包最大容量int[] weight = {3, 4, 2}; // 物品重量int[] value = {4, 5, 3}; // 物品价值// 初始化 dp 数组int[][] dp = new int[n + 1][bagweight + 1];// 动态规划填充 dp 数组for (int i = 1; i <= n; i++) {for (int j = 0; j <= bagweight; j++) {dp[i][j] = dp[i - 1][j]; // 不选择当前物品if (j >= weight[i - 1]) {dp[i][j] = Math.max(dp[i][j], dp[i][j - weight[i - 1]] + value[i - 1]); // 选择或不选择当前物品}}}// 输出最大价值System.out.println("最大价值: " + dp[n][bagweight]);// 回溯找到具体的物品List<Integer> selectedItems = new ArrayList<>();int i = n, j = bagweight;while (i > 0 && j >= 0) {if (j >= weight[i - 1] && dp[i][j] != dp[i - 1][j]) {selectedItems.add(i - 1); // 物品索引从0开始j -= weight[i - 1];}i--;}// 输出选择的物品System.out.print("选择的物品: ");for (int item : selectedItems) {System.out.print(item + " (重量: " + weight[item] + ", 价值: " + value[item] + ") ");}System.out.println();}
}
-
0-1背包问题:
- 每个物品只能选择一次。
- 回溯逻辑中,一旦确定选择了某个物品,就从当前的背包容量中减去该物品的重量,并且继续回溯下一个物品。
-
完全背包问题:
- 每个物品可以选择多次,直到背包容量不允许为止。
- 回溯逻辑中,需要检查在当前背包容量下可以选择该物品的次数。这通常涉及到一个循环,直到背包容量不足以再添加一个该物品为止。