如何在 Java 中利用数组实现简单的动态规划背包问题（0-1 Knapsack）价值矩阵

欢迎各位小伙伴来到golang学习网，相聚于此都是缘哈哈哈！今天我给大家带来《如何在 Java 中利用数组实现简单的动态规划背包问题（0-1 Knapsack）价值矩阵》，这篇文章主要讲到等等知识，如果你对文章相关的知识非常感兴趣或者正在自学，都可以关注我，我会持续更新相关文章！当然，有什么建议也欢迎在评论留言提出！一起学习！

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 背包的“每件至多选一次”语义。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~