Java中用数组实现0-1背包问题的核心是构建二维dpi矩阵，表示前i个物品、容量w下的最大价值；初始化dpn+1，首行首列置0；按状态转移方程逐行填表；可回溯选中物品；还可优化为一维滚动数组。
在 java 中用数组实现 0-1 背包问题的价值矩阵，核心是构建一个二维数组 dp[i][w]，表示前 i 个物品、背包容量为 w 时能获得的最大价值。它不依赖递归或额外库，仅靠循环和状态转移，适合初学动态规划理解“填表”过程。
定义二维 dp 数组并初始化
设物品数量为 n，背包最大容量为 capacity。声明 int[][] dp = new int[n + 1][capacity + 1] —— 行数 n+1 是为了包含“0 个物品”的边界情况，列数 capacity+1 覆盖从 0 到满容量的所有可能。
首行（i = 0）全为 0，因为没物品时价值恒为 0；首列（w = 0）也全为 0，因为容量为 0 时无法装入任何物品。
按状态转移方程逐行填充矩阵
对每个物品 i（从 1 到 n）和每个容量 w（从 0 到 capacity），按以下逻辑更新：
- 若当前物品重量
weight[i-1] > w：装不下，继承上一行结果 →dp[i][w] = dp[i-1][w] - 否则：可选“不装”或“装”，取较大值 →
dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1])
注意：物品数组下标从 0 开始，所以第 i 行对应第 i-1 个物品（如 weight[i-1]）。
获取最大价值与回溯方案（可选）
填完后，dp[n][capacity] 就是最大总价值。
若需知道哪些物品被选中，可从 dp[n][capacity] 反向追踪：
- 从
i = n, w = capacity开始 - 若
dp[i][w] != dp[i-1][w]，说明第i-1个物品被选中，将它加入结果，并令w -= weight[i-1] - 否则跳过，仅令
i-- - 重复直到
i == 0
空间优化：滚动数组（一维实现）
观察发现每行只依赖上一行，可用一维数组 int[] dp = new int[capacity + 1] 替代二维。关键点是内层循环必须从 capacity 递减到 weight[i]，避免同一物品被重复使用：
for (int w = capacity; w >= weight[i]; w--) {dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);}
这样既节省内存，又保持 0-1 背包的“每件至多选一次”语义。
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
