Java实现背包问题详解（小白也能学会的01背包与动态规划算法）

解决思路：动态规划

我们可以使用动态规划来高效地解决这个问题。核心思想是：构建一个二维数组 dp[i][w]，表示前 i 个物品在背包容量为 w 时能获得的最大价值。

状态转移方程如下：

if (weight[i-1] > w) {    dp[i][w] = dp[i-1][w];} else {    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i-1]] + value[i-1]);}

完整Java代码实现

下面是一个完整的 Java背包问题 实现示例：

public class Knapsack {    public static int knapsack(int W, int[] weights, int[] values, int n) {        // 创建dp表，dp[i][w] 表示前i个物品在容量w下的最大价值        int[][] dp = new int[n + 1][W + 1];        // 初始化：当没有物品或容量为0时，价值为0        for (int i = 0; i <= n; i++) {            dp[i][0] = 0;        }        for (int w = 0; w <= W; w++) {            dp[0][w] = 0;        }        // 填充dp表        for (int i = 1; i <= n; i++) {            for (int w = 1; w <= W; w++) {                if (weights[i - 1] <= w) {                    // 可以选择当前物品                    dp[i][w] = Math.max(                        dp[i - 1][w],                         dp[i - 1][w - weights[i - 1]] + values[i - 1]                    );                } else {                    // 不能选择当前物品                    dp[i][w] = dp[i - 1][w];                }            }        }        return dp[n][W];    }    public static void main(String[] args) {        int[] values = {60, 100, 120};        int[] weights = {10, 20, 30};        int W = 50;        int n = values.length;        System.out.println("最大价值为: " + knapsack(W, weights, values, n));        // 输出：最大价值为: 220    }}

代码说明

• 初始化：第一行和第一列都设为0，因为没有物品或没有容量时无法获得价值。
• 状态转移：对每个物品，判断是否能放入当前容量的背包。如果能放，就比较“放”和“不放”哪个价值更大。
• 结果：最终答案保存在 dp[n][W] 中。

总结

通过本教程，你已经掌握了如何用 Java语言 解决经典的 01背包问题。这不仅是 动态规划算法 的入门必学内容，也是提升编程思维的重要一步。建议你动手敲一遍代码，加深理解。

如果你正在准备面试或学习算法，那么这个 Java背包问题 的实现一定会对你有所帮助！

提示：你可以尝试优化空间复杂度，将二维dp数组压缩为一维，进一步提升效率。