跳到主要内容

背包问题

背包问题（Knapsack Problem）是组合优化中的经典问题，也是动态规划最具代表性的应用之一。给定一组物品，每个物品具有重量和价值，要求在限定的总重量内，选择物品使得总价值最大。

问题定义​

问题描述：有一个容量为 WW 的背包和 nn 个物品，第 ii 个物品的重量为 w[i]w[i]，价值为 v[i]v[i]。目标是选择一些物品装入背包，在总重量不超过 WW 的前提下，使总价值最大化。

关键约束：

  • 每个物品要么选，要么不选（0-1背包）
  • 不能只选物品的一部分
  • 所有物品只能选择有限次或无限次（取决于问题类型）

0-1 背包问题​

0-1 背包是最基础的背包问题：每个物品最多选一次。

问题分析​

考虑第 ii 个物品时，只有两种选择：

  1. 不选：问题转化为前 i−1i-1 个物品在容量 jj 下的最优解
  2. 选：问题转化为前 i−1i-1 个物品在容量 j−w[i]j-w[i] 下的最优解，加上 v[i]v[i]

这就是最优子结构性质：问题的最优解包含子问题的最优解。

状态定义​

设 dp[i][j]dp[i][j] 表示考虑前 ii 个物品，在容量为 jj 时能获得的最大价值。

状态转移方程​

对于第 ii 个物品和容量 jj：

dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

  • dp[i−1][j]dp[i-1][j]：不选第 ii 个物品
  • dp[i−1][j−w[i]]+v[i]dp[i-1][j-w[i]] + v[i]：选第 ii 个物品（前提是 j≥w[i]j \ge w[i]）

边界条件：

  • dp[0][j]=0dp[0][j] = 0：没有物品可选
  • dp[i][0]=0dp[i][0] = 0：容量为0

二维数组实现​

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    // dp[0][j] = 0 已默认初始化
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            // 不选第 i 个物品
            dp[i][j] = dp[i - 1][j];
            
            // 选第 i 个物品（如果放得下）
            if (j >= weights[i - 1]) {
                dp[i][j] = Math.max(dp[i][j], 
                    dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    return dp[n][capacity];
}

算法分析：

  • 时间复杂度：O(n×W)O(n \times W)，其中 nn 是物品数量，WW 是背包容量
  • 空间复杂度：O(n×W)O(n \times W)

空间优化：一维数组​

观察状态转移方程，计算 dp[i][j]dp[i][j] 只需要 dp[i−1][⋅]dp[i-1][\cdot] 这一行。因此可以用一维数组，但需要注意遍历顺序。

为什么要逆序遍历？

计算 dp[j]dp[j] 时需要用到 dp[j−w[i]]dp[j-w[i]]，如果正序遍历，dp[j−w[i]]dp[j-w[i]] 已经被更新为当前行的值（选了第 ii 个物品），这样会导致第 ii 个物品被重复选择。逆序遍历可以确保 dp[j−w[i]]dp[j-w[i]] 是上一轮的值。

public int knapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        // 逆序遍历，确保第 i 个物品只选一次
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

空间优化后的复杂度：

  • 时间复杂度：O(n×W)O(n \times W)
  • 空间复杂度：O(W)O(W)

如何求具体方案？​

如果需要知道选择了哪些物品，需要回溯：

public List<Integer> getSelectedItems(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[][] dp = new int[n + 1][capacity + 1];
    
    // 填充 dp 表（同上）
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= weights[i - 1]) {
                dp[i][j] = Math.max(dp[i][j], 
                    dp[i - 1][j - weights[i - 1]] + values[i - 1]);
            }
        }
    }
    
    // 回溯找出选择的物品
    List<Integer> selected = new ArrayList<>();
    int j = capacity;
    for (int i = n; i >= 1; i--) {
        // 如果 dp[i][j] != dp[i-1][j]，说明选了第 i 个物品
        if (dp[i][j] != dp[i - 1][j]) {
            selected.add(i - 1);  // 物品索引
            j -= weights[i - 1];  // 减去该物品重量
        }
    }
    
    return selected;
}

完全背包问题​

完全背包问题中，每个物品可以选择无限次。

与 0-1 背包的区别​

关键区别在于遍历顺序。0-1 背包逆序遍历是为了防止重复选择，而完全背包允许重复选择，所以需要正序遍历。

状态转移方程​

dp[j]=max⁡(dp[j],dp[j−w[i]]+v[i])dp[j] = \max(dp[j], dp[j-w[i]] + v[i])

实现​

public int completeKnapsack(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        // 正序遍历，允许重复选择同一物品
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[capacity];
}

为什么正序遍历可以重复选择？

正序遍历时，计算 dp[j]dp[j] 用到的 dp[j−w[i]]dp[j-w[i]] 可能已经在当前轮次更新过，这意味着第 ii 个物品可能已经被选择过，从而实现了重复选择。

示例分析​

假设背包容量为 10，物品为：重量 2，价值 5。

正序遍历过程：

  • dp[2]=max⁡(dp[2],dp[0]+5)=5dp[2] = \max(dp[2], dp[0] + 5) = 5（选了1个）
  • dp[4]=max⁡(dp[4],dp[2]+5)=10dp[4] = \max(dp[4], dp[2] + 5) = 10（选了2个）
  • dp[6]=max⁡(dp[6],dp[4]+5)=15dp[6] = \max(dp[6], dp[4] + 5) = 15（选了3个）
  • ...

这样每个物品可以被选择多次。

多重背包问题​

多重背包问题中，每个物品有数量限制，第 ii 个物品最多选 k[i]k[i] 个。

基本解法​

将有限数量的物品拆分成多个单独的物品，转化为 0-1 背包问题。

public int multipleKnapsack(int[] weights, int[] values, int[] counts, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        // 将 counts[i] 个物品展开
        for (int k = 0; k < counts[i]; k++) {
            // 0-1 背包的逆序遍历
            for (int j = capacity; j >= weights[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }
    }
    
    return dp[capacity];
}

时间复杂度：O(W×∑k[i])O(W \times \sum k[i])，当数量很大时效率较低。

二进制优化​

将数量 kk 拆分成 1,2,4,…,2m,k−2m+1+11, 2, 4, \ldots, 2^m, k - 2^{m+1} + 1 的组合，可以将时间复杂度优化到 O(W×∑log⁡k[i])O(W \times \sum \log k[i])。

原理：任何整数都可以表示为若干个 2 的幂次之和。

public int multipleKnapsackBinary(int[] weights, int[] values, int[] counts, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];
    
    for (int i = 0; i < n; i++) {
        // 二进制拆分
        int count = counts[i];
        for (int k = 1; k <= count; k *= 2) {
            int num = Math.min(k, count);
            int w = weights[i] * num;
            int v = values[i] * num;
            
            for (int j = capacity; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
            
            count -= num;
        }
    }
    
    return dp[capacity];
}

分组背包问题​

分组背包问题中，物品被分成若干组，每组最多选一个物品。

状态转移​

dp[j]=max⁡(dp[j],dp[j−w[k]]+v[k])dp[j] = \max(dp[j], dp[j-w[k]] + v[k])，其中 kk 是当前组的物品。

实现​

public int groupKnapsack(List<List<int[]>> groups, int capacity) {
    int[] dp = new int[capacity + 1];
    
    for (List<int[]> group : groups) {
        // 每组只能选一个，逆序遍历
        for (int j = capacity; j >= 0; j--) {
            for (int[] item : group) {
                int w = item[0], v = item[1];
                if (j >= w) {
                    dp[j] = Math.max(dp[j], dp[j - w] + v);
                }
            }
        }
    }
    
    return dp[capacity];
}

应用：零钱兑换​

零钱兑换是背包问题的常见变体。

零钱兑换 I：最少硬币数（LeetCode 322）​

给定不同面额的硬币和总金额，计算凑成总金额所需的最少硬币数。

思路：完全背包问题，求最小值。

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);  // 初始化为较大值
    dp[0] = 0;
    
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] = Math.min(dp[j], dp[j - coin] + 1);
        }
    }
    
    return dp[amount] > amount ? -1 : dp[amount];
}

零钱兑换 II：组合数（LeetCode 518）​

计算凑成总金额的不同组合数。

思路：完全背包问题，求方案数。

public int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;  // 凑成金额 0 有 1 种方案
    
    for (int coin : coins) {
        for (int j = coin; j <= amount; j++) {
            dp[j] += dp[j - coin];
        }
    }
    
    return dp[amount];
}

注意：外层循环遍历硬币，内层循环遍历金额，这样可以保证不会重复计算排列。例如，[1,2] 和 [2,1] 会被视为同一种组合。

如果要求排列数（[1,2] 和 [2,1] 算两种），则需要交换循环顺序。

应用：分割等和子集（LeetCode 416）​

给定一个只包含正整数的数组，判断是否可以将其分割成两个子集，使得两个子集的和相等。

思路：转化为 0-1 背包问题，判断是否可以选出一些数，使其和等于总和的一半。

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    
    if (sum % 2 != 0) return false;  // 总和为奇数，无法平分
    
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
}

应用：目标和（LeetCode 494）​

给定一个数组和一个目标值，可以在每个数前加 + 或 -，计算有多少种方式可以得到目标值。

思路：设正数和为 PP，负数和为 NN，则 P−N=targetP - N = target，且 P+N=sumP + N = sum。解得 P=(target+sum)/2P = (target + sum) / 2。问题转化为选择一些数使其和为 PP。

public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int num : nums) {
        sum += num;
    }
    
    // target + sum 必须是非负偶数
    if ((target + sum) % 2 != 0 || target + sum < 0) {
        return 0;
    }
    
    int bagSize = (target + sum) / 2;
    int[] dp = new int[bagSize + 1];
    dp[0] = 1;
    
    for (int num : nums) {
        for (int j = bagSize; j >= num; j--) {
            dp[j] += dp[j - num];
        }
    }
    
    return dp[bagSize];
}

背包问题总结​

遍历顺序总结​

问题类型外层循环内层循环原因
0-1 背包物品容量（逆序）防止重复选择
完全背包物品容量（正序）允许重复选择
分组背包组容量（逆序）→ 组内物品每组只选一个
组合数物品容量（正序）保证不重复计算排列
排列数容量物品允许排列

状态转移总结​

目标状态转移
最大价值dp[j]=max⁡(dp[j],dp[j−w]+v)dp[j] = \max(dp[j], dp[j-w] + v)
最小数量dp[j]=min⁡(dp[j],dp[j−w]+1)dp[j] = \min(dp[j], dp[j-w] + 1)
方案数dp[j]+=dp[j−w]dp[j] += dp[j-w]
是否可行dp[j]=dp[j]∨dp[j−w]dp[j] = dp[j] \lor dp[j-w]

初始化技巧​

  • 求最大价值：dp[0]=0dp[0] = 0，其余为 0
  • 求最小数量：dp[0]=0dp[0] = 0，其余为 ∞\infty
  • 求方案数：dp[0]=1dp[0] = 1，其余为 0
  • 求是否可行：dp[0]=truedp[0] = true，其余为 false

练习​

  1. LeetCode 416：分割等和子集（转化为 0-1 背包）
  2. LeetCode 322：零钱兑换（完全背包求最小值）
  3. LeetCode 518：零钱兑换 II（完全背包求方案数）
  4. LeetCode 494：目标和（0-1 背包求方案数）
  5. LeetCode 377：组合总和 IV（完全背包求排列数）
  6. LeetCode 474：一和零（二维背包）
  7. LeetCode 1049：最后一块石头的重量 II（类似分割等和子集）
  8. LeetCode 1449：数位成本和为目标值的最大数字（完全背包 + 记录路径）