0-1 背包问题的 Java 实现

1. 简介

背包问题（Knapsack Problem）是一个经典的组合优化问题，在资源分配、任务调度、加密算法等领域都有广泛应用。本文将带你用 Java 实现 0-1 背包问题，并对比递归与动态规划两种解法，帮你避开常见性能“坑”。

2. 问题描述

我们有一组物品，每个物品都有自己的重量（weight）和价值（value）：

目标是把这些物品装进一个背包，但背包有最大承重限制：

✅ 核心目标：在总重量不超过限制的前提下，使装入物品的总价值最大化。

比如图中，选择 5kg 和 6kg 的物品，总重 11kg（≤11kg），总价值 $40，就是最优解。

⚠️ 本文聚焦 0-1 背包问题，其规则是：

每件物品只能选或不选（不能选半个）
每件物品只能拿一次（不能重复拿）

这也是最常见、最基础的变体。

3. 数学建模

设共有 n 件物品，背包承重上限为 W，第 i 件物品的重量为 wᵢ，价值为 vᵢ。定义状态 M(i, w) 表示前 i 件物品在重量限制 w 下能获得的最大价值。

优化目标为：

✅ 这是一个 NP-hard 问题，意味着目前没有已知的多项式时间算法能解决所有情况。

❌ 但好消息是：我们可以用动态规划实现一个伪多项式时间（pseudo-polynomial time）解法，时间复杂度为 O(nW)，在 W 不太大时非常实用。

4. 递归解法

核心思想是分治：对第 n 件物品，有两种选择：

不拿：最大价值 = 前 n-1 件物品在重量 W 下的最大价值
拿：价值 = 第 n 件的价值 + 前 n-1 件在重量 (W - wₙ) 下的最大价值

取两者最大值即可。递推公式如下：

Java 实现如下：

int knapsackRec(int[] w, int[] v, int n, int W) {
    if (n <= 0) { 
        return 0; 
    } else if (w[n - 1] > W) {
        return knapsackRec(w, v, n - 1, W);
    } else {
        return Math.max(knapsackRec(w, v, n - 1, W), 
                        v[n - 1] + knapsackRec(w, v, n - 1, W - w[n - 1]));
    }
}

⚠️ 踩坑警告：这个递归版本虽然简洁，但存在大量重复计算。时间复杂度高达 **O(2ⁿ)**，n 稍大（比如 40）就会卡死。生产环境绝对不能直接用！

5. 动态规划解法

动态规划的核心是“空间换时间”——用一个二维数组缓存所有子问题的解，避免重复计算。

解法思路

创建一个 (n+1) × (W+1) 的二维数组 m
m[i][j] 表示：从前 i 件物品中选，总重不超过 j 时的最大价值
使用自底向上方式填表

Java 实现

int knapsackDP(int[] w, int[] v, int n, int W) {
    if (n <= 0 || W <= 0) {
        return 0;
    }

    int[][] m = new int[n + 1][W + 1];
    
    // 初始化：0 件物品时价值为 0
    for (int j = 0; j <= W; j++) {
        m[0][j] = 0;
    }

    // 填表：逐个物品、逐个重量遍历
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) { 
            // 当前物品超重，不能选
            if (w[i - 1] > j) {
                m[i][j] = m[i - 1][j];
            } 
            // 否则，选价值更大的方案
            else {
                m[i][j] = Math.max(
                    m[i - 1][j], 
                    m[i - 1][j - w[i - 1]] + v[i - 1]
                );
            }
        }
    }
    return m[n][W];
}

✅ 优势分析：

时间复杂度：**O(nW)**，相比递归是质的飞跃
空间复杂度：**O(nW)**，可接受
适合 W 不是特别大的场景（比如 W < 10000）

⚠️ 进阶提示：如果内存紧张，可以用滚动数组优化空间到 O(W)，思路是只保留上一行的状态。

6. 总结

0-1 背包问题是典型的动态规划应用场景
递归写法简单但性能极差，仅适合理解思路
动态规划通过状态表避免重复计算，是工业级解法
时间复杂度 O(nW) 是伪多项式，注意 W 的规模

所有示例代码已托管至 GitHub：https://github.com/baeldung/tutorials（路径：algorithms-modules/algorithms-miscellaneous-5）

Persistence

REST

Security