假设你需要从一个装满金条的宝库中选择带走一些金条，但背包容量有限。每根金条有重量和价值，如何在不超过背包容量的前提下，使带走的价值最大？这个看似简单的选择问题，实际上蕴含着动态规划最核心的思想——如何在约束条件下做出最优决策。

背包问题（Knapsack Problem）是组合优化领域最经典的问题之一，最早可以追溯到1897年数学家G. B. Mathews发表的论文《On the partition of numbers》。1972年，Richard Karp在其著名的论文中将子集和问题（背包问题的特例）列为21个NP完全问题之一，奠定了背包问题在计算机科学中的重要地位。

背包问题的本质：约束下的最优决策

背包问题的核心特征是在有限约束下做出最优选择。根据物品选择方式的限制，背包问题主要分为三类：

01背包：每种物品只有一件，要么选要么不选——“0"或"1"的二元决策。

完全背包：每种物品有无限件，可以选择任意多次。

多重背包：每种物品有有限件，选择次数有上限。

理解这三类问题的关键在于把握状态转移的微妙差异——同一件物品能否被重复选择，决定了遍历顺序的根本不同。

背包问题示意图

图片来源: Wikipedia - Knapsack Problem

01背包：动态规划的入门范式

状态定义与转移方程

01背包是最基础的背包问题。设 dp[i][j] 表示考虑前 i 件物品、背包容量为 j 时能获得的最大价值。对于第 i 件物品，只有两种选择：

  • 不选：dp[i][j] = dp[i-1][j]
  • 选（前提是 j >= weight[i]）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]

综合起来，状态转移方程为：

$$dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)$$
// 01背包 - 二维数组实现
public int knapsack01(int W, int[] weights, int[] values) {
    int n = weights.length;
    int[][] dp = new int[n + 1][W + 1];
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; 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][W];
}

空间优化：一维数组的关键技巧

观察状态转移方程，dp[i][j] 只依赖于 dp[i-1][...]，即上一行的数据。这意味着可以用一维数组滚动更新。但关键在于遍历顺序——必须从大到小遍历容量，确保每个物品只被选择一次。

// 01背包 - 一维数组优化
public int knapsack01Optimized(int W, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < weights.length; i++) {
        // 关键：从大到小遍历，保证每个物品只选一次
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

为什么必须从大到小遍历？假设物品重量为2，从小到大遍历时，dp[2] 更新后，dp[4] 会基于已更新的 dp[2] 再次计算，导致同一物品被选了两次。从大到小遍历则保证了更新 dp[j] 时，dp[j-w] 还是上一轮的值。

LeetCode 416. 分割等和子集

题目描述：给定正整数数组 nums，判断能否将其分割成两个子集，使得两个子集的和相等。

解题思路：问题等价于：能否从数组中选出若干元素，使其和等于总和的一半。这转化为一个"存在性"的01背包问题——目标是恰好装满容量为 sum/2 的背包。

class Solution {
    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;  // 容量为0总是可达（不选任何元素）
        
        for (int num : nums) {
            // 从大到小遍历，保证每个数字只用一次
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

复杂度分析：时间复杂度 $O(n \times target)$，空间复杂度 $O(target)$。

LeetCode 494. 目标和

题目描述：给数组中每个数字添加 + 或 -，使得表达式的结果等于目标值 target，求有多少种方法。

解题思路：设添加 + 的数字之和为 P，添加 - 的数字之和为 N，则：

  • P + N = sum（所有数字之和）
  • P - N = target

解得 P = (sum + target) / 2。问题转化为：从数组中选择若干数字，使其和恰好为 P 的方案数。

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) sum += num;
        
        // 目标值超过总和或无法整除
        if (Math.abs(target) > sum || (sum + target) % 2 != 0) {
            return 0;
        }
        
        int positiveSum = (sum + target) / 2;
        int[] dp = new int[positiveSum + 1];
        dp[0] = 1;  // 和为0有1种方案（不选任何元素）
        
        for (int num : nums) {
            for (int j = positiveSum; j >= num; j--) {
                dp[j] += dp[j - num];
            }
        }
        
        return dp[positiveSum];
    }
}

LeetCode 474. 一和零

题目描述：给定字符串数组 strs 和整数 m、n，找出最大子集长度，使得子集中所有字符串的 0 和 1 的总数分别不超过 m 和 n。

解题思路：这是一个二维01背包问题——背包有两个容量约束（0 的数量和 1 的数量）。

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        
        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }
            
            // 二维背包，两个维度都从大到小遍历
            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }
        
        return dp[m][n];
    }
}

LeetCode 1049. 最后一块石头的重量 II

题目描述：有一堆石头，每次选两块相撞，重量小的粉碎，重量大的减去小的重量。求最后剩下石头的最小可能重量。

解题思路：将石头分成两堆，使得两堆重量差最小。这等价于：从数组中选若干元素，使其和尽可能接近总和的一半。

class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) sum += stone;
        
        int target = sum / 2;
        int[] dp = new int[target + 1];
        
        for (int stone : stones) {
            for (int j = target; j >= stone; j--) {
                dp[j] = Math.max(dp[j], dp[j - stone] + stone);
            }
        }
        
        // 一堆重量为dp[target]，另一堆为sum - dp[target]
        return sum - 2 * dp[target];
    }
}

完全背包：无限选择的智慧

状态转移的关键差异

完全背包与01背包的唯一区别在于：每种物品可以选择无限次。这导致状态转移方程变为：

$$dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i)$$

注意第二个选项是 dp[i][j-w] 而非 dp[i-1][j-w]——因为选了第 i 件物品后，还可以继续选同一件物品。

在一维数组优化中，这意味着遍历顺序从小到大：

// 完全背包 - 一维数组实现
public int knapsackComplete(int W, int[] weights, int[] values) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < weights.length; i++) {
        // 关键：从小到大遍历，允许同一物品选多次
        for (int j = weights[i]; j <= W; j++) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    
    return dp[W];
}

01背包与完全背包的本质区别

特性 01背包 完全背包
物品数量 每种一件 每种无限
一维遍历顺序 从大到小 从小到大
转移方程 dp[j] = max(dp[j], dp[j-w] + v) dp[j] = max(dp[j], dp[j-w] + v)
核心差异 dp[j-w] 来自上一轮 dp[j-w] 来自本轮

LeetCode 518. 零钱兑换 II

题目描述：给定不同面额的硬币和总金额，计算凑成总金额的硬币组合数。

解题思路：这是一个求方案数的完全背包问题。注意区分"组合数”（顺序不重要）和"排列数"（顺序重要）。

class Solution {
    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];
    }
}

关键理解：外层遍历硬币、内层遍历金额，保证每种面额的硬币按固定顺序考虑，从而得到组合数。如果交换两层循环，则得到排列数。

LeetCode 322. 零钱兑换

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

解题思路：求最小值的完全背包问题。初始化时将不可能的情况设为无穷大。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 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] == Integer.MAX_VALUE - 1 ? -1 : dp[amount];
    }
}

LeetCode 279. 完全平方数

题目描述：给定正整数 n，找到若干个完全平方数使其和为 n，且个数最少。

解题思路：将完全平方数视为"硬币面额"，转化为完全背包问题。

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE - 1);
        dp[0] = 0;
        
        // 完全平方数作为"物品"
        for (int i = 1; i * i <= n; i++) {
            int square = i * i;
            for (int j = square; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - square] + 1);
            }
        }
        
        return dp[n];
    }
}

LeetCode 139. 单词拆分

题目描述：给定字符串 s 和字典 wordDict，判断 s 是否可以由字典中的单词拼接而成。

解题思路：将单词视为"物品"，字符串位置视为"背包容量"。dp[i] 表示前 i 个字符能否被拼接。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;  // 空字符串总是可达
        
        // 外层遍历容量（字符串位置）
        for (int i = 1; i <= n; i++) {
            // 内层遍历物品（单词）
            for (String word : wordDict) {
                int len = word.length();
                if (i >= len && dp[i - len] 
                    && s.substring(i - len, i).equals(word)) {
                    dp[i] = true;
                    break;  // 只要找到一种方案即可
                }
            }
        }
        
        return dp[n];
    }
}

LeetCode 377. 组合总和 IV

题目描述：给定数组和目标值，求组合的个数（不同顺序视为不同组合，实际上是排列数）。

解题思路：求排列数，需要交换两层循环的顺序——外层遍历容量，内层遍历物品。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        // 外层遍历容量，内层遍历物品 → 求排列数
        for (int j = 1; j <= target; j++) {
            for (int num : nums) {
                if (j >= num) {
                    dp[j] += dp[j - num];
                }
            }
        }
        
        return dp[target];
    }
}

关键理解：组合数 vs 排列数的区别在于遍历顺序。

  • 组合数：外层物品、内层容量（每种物品按固定顺序考虑）
  • 排列数：外层容量、内层物品（每个容量可以以任意顺序使用物品）

多重背包：有限选择的扩展

多重背包是01背包的扩展——每种物品有有限件。最直接的解法是将每种物品"拆分"成多个01物品，但效率较低。优化方法是使用二进制拆分，将 $k$ 件物品拆分成 $1, 2, 4, ..., 2^m, k-2^m$ 的组合，将时间复杂度从 $O(n \times W \times k)$ 优化到 $O(n \times W \times \log k)$。

// 多重背包 - 二进制优化
public int knapsackMultiple(int W, int[] weights, int[] values, int[] counts) {
    int[] dp = new int[W + 1];
    
    for (int i = 0; i < weights.length; i++) {
        // 二进制拆分
        for (int k = 1; k <= counts[i]; k *= 2) {
            int num = Math.min(k, counts[i] - k + 1);
            int w = weights[i] * num;
            int v = values[i] * num;
            
            for (int j = W; j >= w; j--) {
                dp[j] = Math.max(dp[j], dp[j - w] + v);
            }
        }
    }
    
    return dp[W];
}

背包问题题目分类

类型 题目编号 难度 核心技巧
01背包-存在性 416 Medium 能否恰好装满
01背包-方案数 494 Medium 目标和转化
01背包-二维 474 Medium 两个容量约束
01背包-最优值 1049 Medium 分成两堆差最小
完全背包-方案数 518 Medium 组合数遍历顺序
完全背包-最小值 322, 279 Medium 初始化无穷大
完全背包-存在性 139 Medium 单词拼接
完全背包-排列数 377 Medium 交换遍历顺序
完全背包-最大值 343 Medium 整数拆分
变形-分组背包 1155 Medium 每组选一个

代码模板速查

01背包模板

// 求最大价值
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 求方案数
int[] dp = new int[W + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {
        dp[j] += dp[j - weight[i]];
    }
}

// 求是否存在
boolean[] dp = new boolean[W + 1];
dp[0] = true;
for (int i = 0; i < n; i++) {
    for (int j = W; j >= weight[i]; j--) {
        dp[j] = dp[j] || dp[j - weight[i]];
    }
}

完全背包模板

// 求最大价值
int[] dp = new int[W + 1];
for (int i = 0; i < n; i++) {
    for (int j = weight[i]; j <= W; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 求最小数量
int[] dp = new int[W + 1];
Arrays.fill(dp, Integer.MAX_VALUE - 1);
dp[0] = 0;
for (int i = 0; i < n; i++) {
    for (int j = weight[i]; j <= W; j++) {
        dp[j] = Math.min(dp[j], dp[j - weight[i]] + 1);
    }
}

// 求组合数
int[] dp = new int[W + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = weight[i]; j <= W; j++) {
        dp[j] += dp[j - weight[i]];
    }
}

// 求排列数
int[] dp = new int[W + 1];
dp[0] = 1;
for (int j = 1; j <= W; j++) {
    for (int i = 0; i < n; i++) {
        if (j >= weight[i]) {
            dp[j] += dp[j - weight[i]];
        }
    }
}

实战技巧与常见陷阱

技巧一：识别背包问题的特征

  • 有"选择"的概念（选或不选）
  • 有"容量"约束
  • 求最优解、方案数或存在性

技巧二：确定遍历顺序

  • 01背包：从大到小（每个物品只选一次）
  • 完全背包：从小到大（每个物品可选多次）
  • 组合数：外层物品、内层容量
  • 排列数：外层容量、内层物品

技巧三：初始化的处理

  • 求最大值：初始化为0
  • 求最小值：初始化为无穷大
  • 求方案数：dp[0] = 1，其余为0
  • 求存在性：dp[0] = true，其余为false

陷阱一：恰好装满 vs 不超过容量

  • 恰好装满：dp[0] 初始化为基准值，其余初始化为无效值
  • 不超过容量：全部初始化为基准值

陷阱二：组合数 vs 排列数

  • 组合数：外层遍历物品
  • 排列数：外层遍历容量

陷阱三：整数溢出

  • 方案数可能很大，注意使用 long 类型或取模
  • 求最小值时，“无穷大"应设为 Integer.MAX_VALUE - 1 避免加法溢出

刷题建议

入门顺序：416 → 494 → 322 → 518

进阶挑战：474 → 1049 → 279 → 139

高难度：377 → 343 → 1155

背包问题是理解动态规划的绝佳入口。从朴素递归到记忆化搜索，从二维数组到一维优化，从01背包到完全背包，每一步优化都蕴含着深刻的思想：空间换时间、状态压缩、遍历顺序的意义。掌握背包问题，不仅是掌握一类题目，更是掌握动态规划的思维范式——如何定义状态、如何推导转移、如何优化实现。

参考资料

  1. Knapsack problem - Wikipedia
  2. 0/1 Knapsack Problem - GeeksforGeeks
  3. Unbounded Knapsack - GeeksforGeeks
  4. Dynamic Programming Patterns - LeetCode Discuss
  5. Knapsack Problem - CP-Algorithms
  6. Hello Algo - 背包问题
  7. Karp, R. M. (1972). “Reducibility Among Combinatorial Problems”