java01背包问题模板

### Java 实现 01 胪包问题的代码模板 以下是基于动态规划方法解决 01 背包问题的经典 Java 实现方式。该算法通过构建 `dp` 表格来记录不同状态下的最优解。 #### 二维 DP 表实现 ```java public class Knapsack { /** * 解决 01 背包问题 * * @param weight 物品重量数组 * @param value 物品价值数组 * @param n 物品数量 * @param W 背包最大承重 * @return 最大价值 */ public static int knapSack(int[] weight, int[] value, int n, int W) { // 创建 dp 表，初始化为 0 int[][] dp = new int[n + 1][W + 1]; for (int i = 1; i <= n; i++) { // 遍历物品 for (int j = 0; j <= W; 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]); } } } return dp[n][W]; // 返回最终结果 } public static void main(String[] args) { int[] weight = {2, 3, 4, 5}; // 物品重量 int[] value = {3, 4, 5, 6}; // 物品价值 int W = 10; // 背包最大承重 System.out.println("背包能获得的最大价值为: " + knapSack(weight, value, weight.length, W)); } } ``` 此代码实现了标准的 01 背包问题求解逻辑[^1]。它通过两层嵌套循环分别遍历物品和背包容量，并利用转移方程计算每个状态下能够达到的最大价值。 --- #### 一维优化版 DP 表实现 为了减少空间复杂度，可以采用滚动数组的方式对上述二维表格进行压缩： ```java public class OptimizedKnapsack { /** * 使用一维数组解决 01 背包问题 * * @param weight 物品重量数组 * @param value 物品价值数组 * @param W 背包最大承重 * @return 最大价值 */ public static int optimizedKnapSack(int[] weight, int[] value, int W) { int[] dp = new int[W + 1]; // 初始化一维 dp 数组 for (int i = 0; i < weight.length; i++) { // 遍历物品 for (int j = W; j >= weight[i]; j--) { // 倒序遍历背包容量 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]); } } return dp[W]; // 返回最终结果 } public static void main(String[] args) { int[] weight = {2, 3, 4, 5}; int[] value = {3, 4, 5, 6}; int W = 10; System.out.println("背包能获得的最大价值为: " + optimizedKnapSack(weight, value, W)); } } ``` 在一维版本中，外层循环仍然负责遍历物品，而内层循环则倒序遍历背包容量以避免重复使用同一物品[^1]。这种优化显著降低了内存消耗。 --- ### 关键点解析 - **状态定义**: 设 `dp[i][j]` 表示从前 `i` 个物品中选取若干放入容量为 `j` 的背包所能得到的最大价值。 - **状态转移方程**: \[ dp[i][j] = \begin{cases} dp[i-1][j],&\text{if}\ j<weight[i]\\ \max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i]),&\text{otherwise}. \end{cases} \] - **边界条件**: 初始时设所有 `dp[0][j] = 0` 和 `dp[i][0] = 0`，表示没有任何物品或者背包容量为零的情况[^2]。 ---