【自用】0-1背包问题与完全背包问题的Java实现
引言
背包问题是计算机科学领域的一个经典优化问题，分为多种类型，其中最常见的是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背包问题：
- 每个物品只能选择一次。
- 回溯逻辑中，一旦确定选择了某个物品，就从当前的背包容量中减去该物品的重量，并且继续回溯下一个物品。
-
完全背包问题：
- 每个物品可以选择多次，直到背包容量不允许为止。
- 回溯逻辑中，需要检查在当前背包容量下可以选择该物品的次数。这通常涉及到一个循环，直到背包容量不足以再添加一个该物品为止。