每日算法 — 使用java实现0-1背包：动态规划与空间优化

可莉爸爸 AI算法

引言

背包问题（Knapsack Problem）是算法领域中最经典的动态规划模型之一。想象你是一位探险家，面前摆放着若干件宝物，每件宝物都有重量和价值，而你只有一个容量有限的背包。如何在不超过背包容量的前提下，选择装入哪些宝物，使得总价值最大？这就是0-1背包问题——每件物品要么完整装入（1），要么不装（0），不能分割。

从资源调度、投资组合优化到任务分配，背包问题的思想渗透在计算机科学的各个角落。本文将用Java完整实现0-1背包的动态规划解法，并深入讲解如何从二维DP优化到一维DP，将空间复杂度从O(n×W)降至O(W)。

问题定义

给定n个物品，每个物品有重量weight[i]和价值value[i]，以及一个容量为W的背包。要求选择若干物品装入背包，使得：

  1. 所选物品的总重量不超过背包容量W
  2. 所选物品的总价值尽可能大
  3. 每个物品要么选要么不选（不可重复选取，不可拆分）

示例数据

物品编号 重量 价值
1 2 3
2 3 4
3 4 5
4 5 8

假设背包容量W = 8，最优解为选择物品2（重量3，价值4）和物品4（重量5，价值8），总价值为12。

暴力解法：枚举所有子集

最直观的想法是枚举所有物品的选取组合。对于n个物品，每个物品有选/不选两种状态，共2^n种组合。

// 暴力解法：时间复杂度 O(2^n)，仅用于理解，不适用于大规模数据
public class BruteForceKnapsack {

    public static int knapsack(int[] weight, int[] value, int W, int index) {
        // 边界条件：没有物品或背包容量为0
        if (index < 0 || W == 0) {
            return 0;
        }

        // 如果当前物品重量超过剩余容量，只能不选
        if (weight[index] > W) {
            return knapsack(weight, value, W, index - 1);
        }

        // 两种选择：选当前物品 或 不选当前物品，取价值较大者
        int include = value[index] + knapsack(weight, value, W - weight[index], index - 1);
        int exclude = knapsack(weight, value, W, index - 1);

        return Math.max(include, exclude);
    }
}

暴力解法存在大量重复计算，时间复杂度为指数级。当n = 30时，2^30 ≈ 10亿次运算，显然不可接受。

动态规划：最优子结构与重叠子问题

动态规划适用于具有最优子结构和重叠子问题性质的问题。

  • 最优子结构：问题的最优解包含子问题的最优解。若最优解包含第i个物品，则剩余部分必然是前i-1个物品在容量W - weight[i]下的最优解。
  • 重叠子问题：在递归求解过程中，相同的子问题（相同的i和W组合）被多次计算。

状态定义

定义dp[i][w]为：考虑前i个物品，在背包容量为w时能获得的最大价值。

状态转移方程

对于第i个物品（从1开始计数），有两种决策：

  1. 不选第i个物品：dp[i][w] = dp[i-1][w]
  2. 选第i个物品（前提是weight[i] <= w）：dp[i][w] = dp[i-1][w - weight[i]] + value[i]

状态转移方程：

dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])  // 若 weight[i] <= w
dp[i][w] = dp[i-1][w]                                           // 若 weight[i] > w

初始条件：dp[0][w] = 0（没有物品时价值为0），dp[i][0] = 0（容量为0时价值为0）。

二维DP的Java实现

/**
 * 0-1背包问题：二维动态规划解法
 * 时间复杂度：O(n × W)
 * 空间复杂度：O(n × W)
 */
public class Knapsack2D {

    /**
     * 求解0-1背包问题
     * @param weight 物品重量数组
     * @param value  物品价值数组
     * @param W      背包容量
     * @return 最大价值
     */
    public static int knapsack(int[] weight, int[] value, int W) {
        int n = weight.length;

        // dp[i][w] 表示前i个物品，容量w时的最大价值
        // 数组大小为 (n+1) × (W+1)，第0行和第0列作为初始条件（全0）
        int[][] dp = new int[n + 1][W + 1];

        // 遍历每个物品
        for (int i = 1; i <= n; i++) {
            // 遍历每种容量
            for (int w = 0; w <= W; w++) {
                // 情况1：不选第i个物品（对应数组下标i-1）
                dp[i][w] = dp[i - 1][w];

                // 情况2：选第i个物品，前提是该物品能装入背包
                if (weight[i - 1] <= w) {
                    int includeValue = dp[i - 1][w - weight[i - 1]] + value[i - 1];
                    dp[i][w] = Math.max(dp[i][w], includeValue);
                }
            }
        }

        return dp[n][W];
    }

    /**
     * 回溯求解具体选了哪些物品
     */
    public static void printSelectedItems(int[] weight, int[] value, int W) {
        int n = weight.length;
        int[][] dp = new int[n + 1][W + 1];

        // 先填充dp表
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];
                if (weight[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w], 
                        dp[i - 1][w - weight[i - 1]] + value[i - 1]);
                }
            }
        }

        // 从dp[n][W]回溯
        System.out.println("最优总价值: " + dp[n][W]);
        System.out.print("选中物品编号: ");
        int w = W;
        for (int i = n; i >= 1; i--) {
            // 如果dp[i][w] != dp[i-1][w]，说明选了第i个物品
            if (dp[i][w] != dp[i - 1][w]) {
                System.out.print(i + " ");
                w -= weight[i - 1]; // 减去该物品重量，继续往前找
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] weight = {2, 3, 4, 5};
        int[] value  = {3, 4, 5, 8};
        int W = 8;

        System.out.println("===== 0-1背包问题：二维DP解法 =====");
        System.out.println("物品重量: [2, 3, 4, 5]");
        System.out.println("物品价值: [3, 4, 5, 8]");
        System.out.println("背包容量: " + W);
        System.out.println("最大价值: " + knapsack(weight, value, W));
        printSelectedItems(weight, value, W);
    }
}

运行结果：

===== 0-1背包问题：二维DP解法 =====
物品重量: [2, 3, 4, 5]
物品价值: [3, 4, 5, 8]
背包容量: 8
最大价值: 12
选中物品编号: 4 2

空间优化：滚动数组

观察状态转移方程：dp[i][w]只依赖于上一行dp[i-1][...]的数据，与dp[i-2]及更早的行无关。这意味着我们不需要保存完整的二维表，只需保留两行（当前行和上一行），甚至可以通过巧妙的遍历顺序压缩到一行。

核心洞察

将二维数组压缩为一维：dp[w]表示容量为w时的最大价值。

状态转移变为：

dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

关键问题：如果容量w从小到大遍历（正序），dp[w - weight[i]]可能在本轮已经被更新过，导致同一个物品被重复选取（变成完全背包）。

解决方案：容量w从大到小遍历（逆序）。这样计算dp[w]时，dp[w - weight[i]]仍然是上一轮（i-1个物品）的值，保证每个物品只被选一次。

一维DP的Java实现

/**
 * 0-1背包问题：一维动态规划（滚动数组优化）
 * 时间复杂度：O(n × W)
 * 空间复杂度：O(W)
 */
public class Knapsack1D {

    /**
     * 一维DP求解0-1背包
     * 核心技巧：容量w必须逆序遍历，防止同一物品被重复选取
     */
    public static int knapsack(int[] weight, int[] value, int W) {
        int n = weight.length;
        int[] dp = new int[W + 1]; // 默认初始化为0

        for (int i = 0; i < n; i++) {
            // 必须逆序遍历容量！
            // 若正序遍历，dp[w - weight[i]]可能已被当前物品更新过，
            // 导致物品i被重复选取，违背0-1背包约束
            for (int w = W; w >= weight[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
            }
        }

        return dp[W];
    }

    /**
     * 一维DP同时记录选中物品（使用辅助数组）
     */
    public static int knapsackWithTrace(int[] weight, int[] value, int W) {
        int n = weight.length;
        int[] dp = new int[W + 1];
        // choice[i][w] 记录在面对第i个物品、容量w时是否选择该物品
        boolean[][] choice = new boolean[n][W + 1];

        for (int i = 0; i < n; i++) {
            for (int w = W; w >= weight[i]; w--) {
                int include = dp[w - weight[i]] + value[i];
                if (include > dp[w]) {
                    dp[w] = include;
                    choice[i][w] = true;
                }
            }
        }

        // 回溯找出选中的物品
        System.out.print("选中物品编号: ");
        int w = W;
        for (int i = n - 1; i >= 0; i--) {
            if (w >= 0 && choice[i][w]) {
                System.out.print((i + 1) + " ");
                w -= weight[i];
            }
        }
        System.out.println();

        return dp[W];
    }

    public static void main(String[] args) {
        int[] weight = {2, 3, 4, 5};
        int[] value  = {3, 4, 5, 8};
        int W = 8;

        System.out.println("===== 0-1背包问题：一维DP优化 =====");
        System.out.println("最大价值: " + knapsack(weight, value, W));
        System.out.print("回溯结果: ");
        knapsackWithTrace(weight, value, W);
    }
}

完整项目：带输入输出和多种测试用例

import java.util.Scanner;

/**
 * 0-1背包问题完整实现
 * 包含：二维DP、一维DP优化、多种数据生成策略
 */
public class KnapsackComplete {

    // ============ 核心算法 ============

    public static int knapsack2D(int[] weight, int[] value, int W) {
        int n = weight.length;
        int[][] dp = new int[n + 1][W + 1];
        for (int i = 1; i <= n; i++) {
            for (int w = 0; w <= W; w++) {
                dp[i][w] = dp[i - 1][w];
                if (weight[i - 1] <= w) {
                    dp[i][w] = Math.max(dp[i][w], 
                        dp[i - 1][w - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        return dp[n][W];
    }

    public static int knapsack1D(int[] weight, int[] value, int W) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < weight.length; i++) {
            for (int w = W; w >= weight[i]; w--) {
                dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
            }
        }
        return dp[W];
    }

    // ============ 测试用例 ============

    public static void runTestCases() {
        System.out.println("===== 测试用例集 =====\n");

        // 用例1：基础示例
        int[] w1 = {2, 3, 4, 5};
        int[] v1 = {3, 4, 5, 8};
        int W1 = 8;
        System.out.println("用例1: 重量[2,3,4,5], 价值[3,4,5,8], 容量8");
        System.out.println("二维DP结果: " + knapsack2D(w1, v1, W1) + " (期望: 12)");
        System.out.println("一维DP结果: " + knapsack1D(w1, v1, W1) + " (期望: 12)\n");

        // 用例2：所有物品都能装入
        int[] w2 = {1, 2, 3};
        int[] v2 = {10, 20, 30};
        int W2 = 10;
        System.out.println("用例2: 重量[1,2,3], 价值[10,20,30], 容量10");
        System.out.println("二维DP结果: " + knapsack2D(w2, v2, W2) + " (期望: 60)\n");

        // 用例3：背包容量为0
        int[] w3 = {1, 2, 3};
        int[] v3 = {10, 20, 30};
        int W3 = 0;
        System.out.println("用例3: 容量为0");
        System.out.println("二维DP结果: " + knapsack2D(w3, v3, W3) + " (期望: 0)\n");

        // 用例4：单件物品超重
        int[] w4 = {5, 6, 7};
        int[] v4 = {10, 20, 30};
        int W4 = 4;
        System.out.println("用例4: 所有物品均超重");
        System.out.println("二维DP结果: " + knapsack2D(w4, v4, W4) + " (期望: 0)\n");

        // 用例5：价值密度差异大（贪心会失败，必须用DP）
        int[] w5 = {3, 2, 4};
        int[] v5 = {4, 3, 5};
        int W5 = 5;
        System.out.println("用例5: 贪心陷阱案例，重量[3,2,4], 价值[4,3,5], 容量5");
        System.out.println("贪心策略（按价值密度）会选物品2+...，实际最优是物品1+2");
        System.out.println("DP最优结果: " + knapsack2D(w5, v5, W5) + " (期望: 7)\n");

        // 用例6：大规模随机数据（性能测试）
        int n = 100;
        int[] w6 = new int[n];
        int[] v6 = new int[n];
        java.util.Random rand = new java.util.Random(42);
        for (int i = 0; i < n; i++) {
            w6[i] = rand.nextInt(20) + 1;
            v6[i] = rand.nextInt(100) + 1;
        }
        int W6 = 500;
        long start = System.nanoTime();
        int result6 = knapsack1D(w6, v6, W6);
        long end = System.nanoTime();
        System.out.println("用例6: 100件随机物品, 容量500");
        System.out.println("一维DP结果: " + result6);
        System.out.println("耗时: " + (end - start) / 1_000_000.0 + " ms\n");
    }

    // ============ 交互式输入 ============

    public static void interactiveMode() {
        Scanner sc = new Scanner(System.in);
        System.out.println("===== 0-1背包问题求解器 =====");
        System.out.print("请输入物品数量 n: ");
        int n = sc.nextInt();

        int[] weight = new int[n];
        int[] value = new int[n];

        System.out.println("请依次输入每件物品的重量和价值：");
        for (int i = 0; i < n; i++) {
            System.out.print("物品" + (i + 1) + " 重量: ");
            weight[i] = sc.nextInt();
            System.out.print("物品" + (i + 1) + " 价值: ");
            value[i] = sc.nextInt();
        }

        System.out.print("请输入背包容量 W: ");
        int W = sc.nextInt();

        int result = knapsack1D(weight, value, W);
        System.out.println("\n最大价值为: " + result);
    }

    public static void main(String[] args) {
        // 默认运行测试用例
        runTestCases();

        // 如需交互模式，取消下一行注释
        // interactiveMode();
    }
}

复杂度分析

维度 二维DP 一维DP（优化后）
时间复杂度 O(n × W) O(n × W)
空间复杂度 O(n × W) O(W)
可回溯性 天然支持（保存完整表格） 需辅助数组

时间复杂度分析：两重循环，外层n个物品，内层W种容量，总计算量为n × W。

空间复杂度分析：一维优化利用滚动数组思想，将二维表压缩为一行，并通过逆序遍历保证状态正确性。

注意：0-1背包是伪多项式时间算法。其时间复杂度依赖于数值W而非输入规模（二进制位数）。若W极大（如10^9），DP将不可行，需考虑近似算法或其他策略。

为什么逆序遍历是关键？

正序遍历一维数组时，计算dp[w]用到的dp[w - weight[i]]可能已经被当前物品更新过：

假设 weight = [2], value = [3], W = 4
正序：w=2时 dp[2]=3；w=4时 dp[4]=dp[2]+3=6（物品被选了两次！错误！）
逆序：w=4时 dp[4]=dp[2]+3=3；w=2时 dp[2]=3（每个物品只选一次，正确！）

这一技巧是区分0-1背包与完全背包的核心标志：
– 0-1背包：容量逆序遍历（每个物品只用一次）
– 完全背包：容量正序遍历（每个物品可用无限次）

扩展思考

0-1背包的框架可以延伸解决多种变体：

  • 完全背包：物品数量无限，内层循环正序遍历
  • 多重背包：每件物品有数量限制，可二进制拆分转化为0-1背包
  • 分组背包：每组物品至多选一个，外层加组循环
  • 二维费用背包：物品消耗两种资源（如重量和体积），dp数组升维

总结

0-1背包是理解动态规划的绝佳入口。通过本文，我们掌握了：

  1. 状态定义：dp[i][w]代表前i件物品、容量w时的最大价值
  2. 转移方程：在”选”与”不选”之间取最大值
  3. 空间优化：利用滚动数组将空间从O(nW)压缩至O(W)，核心在于逆序遍历
  4. 代码实践：提供了完整可运行的Java项目，含多种测试用例

动态规划的本质是用空间换时间、用表格记录避免重复计算。0-1背包虽小，却蕴含着算法设计中最核心的思想——在约束条件下做最优决策。

Tagged with: