🎒 背包问题 — 01背包与完全背包

📖 背包问题全景

背包问题是DP最经典的模型族：给定容量为W的背包和n个物品，选择物品使总价值最大（或满足特定条件）。核心区别在于物品的选取方式。背包问题是理解"资源分配"类问题的钥匙。

1. 01背包核心模板

# 01背包：n个物品，容量W，重量w[i]，价值v[i]
# 一维优化: 逆序遍历容量
def knapsack_01(n, W, w, v):
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, w[i] - 1, -1):  # 逆序！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]

# 二维版本（更直观）
def knapsack_01_2d(n, W, w, v):
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            dp[i][j] = dp[i-1][j]  # 不选第i个
            if j >= w[i-1]:
                dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]] + v[i-1])
    return dp[n][W]

2. 完全背包核心模板

# 完全背包：每种物品可无限选取
def knapsack_complete(n, W, w, v):
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(w[i], W + 1):  # 正序！
            dp[j] = max(dp[j], dp[j - w[i]] + v[i])
    return dp[W]

🔬 题目一：分割等和子集（LC 416）

给定正整数数组，判断能否分成两个子集使得两个子集的元素和相等。

思路分析

代码实现

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:  # 奇数不可能等分
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True  # 容量0一定可以凑出
        for num in nums:
            for j in range(target, num - 1, -1):  # 逆序！
                dp[j] = dp[j] or dp[j - num]
        return dp[target]

复杂度分析

时间: O(n * target) 空间: O(target)

🔬 题目二：零钱兑换（LC 322）

给定不同面额的硬币和总金额，计算凑成总金额所需的最少硬币数。每种硬币可无限使用。

思路分析

代码实现

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for j in range(coin, amount + 1):  # 正序！完全背包
                dp[j] = min(dp[j], dp[j - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

复杂度分析

时间: O(n * amount) 空间: O(amount)

🔬 题目三：零钱兑换II（LC 518）

给定不同面额的硬币和总金额，计算凑成总金额的组合数。每种硬币可无限使用。

思路分析

代码实现

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for j in range(coin, amount + 1):
                dp[j] += dp[j - coin]
        return dp[amount]

复杂度分析

时间: O(n * amount) 空间: O(amount)

面试实战技巧

在实际面试中，算法题不仅仅是写代码，更考察沟通、分析和解决问题的能力。以下是一些实战技巧：

1. 解题步骤模板

2. 常见陷阱

3. 代码模板

# 通用解题模板
class Solution:
    def solve(self, input_data):
        # 1. 边界检查
        if not input_data:
            return default_value
        # 2. 初始化
        result = initial_value
        state = initial_state
        # 3. 主循环
        for item in input_data:
            state = transition(state, item)
            result = max/min/update(result, state)
        # 4. 返回结果
        return result

📝 课后练习

1. LC 494 目标和（01背包求方案数）
2. LC 377 组合总和IV（完全背包排列数）
3. LC 1049 最后一块石头的重量II
4. LC 1449 数位成本和为目标值的最大数字

🔑 本课要点回顾

• 01背包逆序遍历容量，完全背包正序遍历容量
• 分割等和子集=01背包恰好装满判定
• 零钱兑换=完全背包求最少数量
• 零钱兑换II=完全背包求方案数
• 先遍历物品->组合数；先遍历容量->排列数

📚 扩展阅读

• 算法导论 背包问题章节
• 背包九讲（经典博客）
• LeetCode背包专题

⚡ 进阶专题：常见变体与扩展

每道经典题目都有丰富的变体。掌握核心模板后，灵活应对变体才是面试的真正挑战。以下列举本课相关的高频变体和扩展思路。

1. 常见题目变体

2. 面试中的沟通技巧

# 面试沟通模板
# 1. 先说思路（1-2分钟）
"这道题我想到两种解法，先说更直观的一种..."

# 2. 分析复杂度（30秒）
"时间复杂度O(n^2)，空间可以优化到O(n)"

# 3. 边写边说
"这里我定义dp[i]表示...，转移方程是..."

# 4. 主动验证
"我用示例走一遍：dp[0]=..., dp[1]=..."

# 5. 讨论优化
"空间还可以进一步优化，因为dp[i]只依赖..."

3. 代码调试检查清单

⚡ 背包问题速查表

背包问题的变体众多，以下速查表帮助你快速定位题目类型和解法。