背包问题九讲，从基础到进阶，彻底掌握动态规划

在算法学习的道路上，背包问题是一类非常经典的动态规划问题，它不仅在编程竞赛中频繁出现，也在实际应用中有着广泛的应用场景，本文将带你从基础到进阶，全面了解背包问题的九种常见变体及其解法，帮助你在动态规划领域更上一层楼。

0/1 背包问题

问题描述：

给定 \( n \) 个物品，每个物品有一个重量 \( w_i \) 和一个价值 \( v_i \)，以及一个容量为 \( W \) 的背包，每个物品只能选择放入或不放入背包中，目标是使得背包中物品的总价值最大。

解法：

使用二维数组dp[i][j] 表示前 \( i \) 个物品在容量为 \( j \) 时的最大价值，状态转移方程为：

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

为了优化空间复杂度，可以使用一维数组dp[j] 进行滚动更新，注意内层循环需要逆序遍历：

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(W, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

完全背包问题

问题描述：

与 0/1 背包类似，但每个物品可以无限次选择放入背包中。

解法：

同样使用一维数组dp[j]，但内层循环需要正序遍历：

def knapsack_complete(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for j in range(weights[i], W + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    return dp[W]

多重背包问题

问题描述：

每个物品有固定的数量限制，即每个物品可以放入背包中的次数有限。

解法：

可以将每个物品拆分成多个 0/1 背包问题来解决，将第 \( i \) 个物品拆分成若干个重量和价值分别为 \( 2^k \times w_i \) 和 \( 2^k \times v_i \) 的物品，\( k \) 满足 \( 2^k \leq c_i \)。

def knapsack_multiple(weights, values, counts, W):
    n = len(weights)
    new_weights = []
    new_values = []
    for i in range(n):
        k = 1
        while k <= counts[i]:
            new_weights.append(k * weights[i])
            new_values.append(k * values[i])
            counts[i] -= k
            k *= 2
        if counts[i] > 0:
            new_weights.append(counts[i] * weights[i])
            new_values.append(counts[i] * values[i])
    
    return knapsack_01(new_weights, new_values, W)

混合背包问题

问题描述：

同时包含 0/1 背包、完全背包和多重背包的混合问题。

解法：

分别处理每种类型的物品，使用相应的解法。

def knapsack_mixed(items, W):
    n = len(items)
    dp = [0] * (W + 1)
    for item in items:
        if item['type'] == '01':
            for j in range(W, item['weight'] - 1, -1):
                dp[j] = max(dp[j], dp[j - item['weight']] + item['value'])
        elif item['type'] == 'complete':
            for j in range(item['weight'], W + 1):
                dp[j] = max(dp[j], dp[j - item['weight']] + item['value'])
        elif item['type'] == 'multiple':
            k = 1
            while k <= item['count']:
                for j in range(W, k * item['weight'] - 1, -1):
                    dp[j] = max(dp[j], dp[j - k * item['weight']] + k * item['value'])
                item['count'] -= k
                k *= 2
            if item['count'] > 0:
                for j in range(W, item['count'] * item['weight'] - 1, -1):
                    dp[j] = max(dp[j], dp[j - item['count'] * item['weight']] + item['count'] * item['value'])
    return dp[W]

二维费用背包问题

问题描述：

每个物品有两个费用 \( w_i \) 和 \( v_i \)，背包也有两个容量 \( W \) 和 \( V \)，目标是在不超过两个容量的情况下最大化物品的总价值。

解法：

使用三维数组dp[i][j][k] 表示前 \( i \) 个物品在容量分别为 \( j \) 和 \( k \) 时的最大价值，状态转移方程为：

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

def knapsack_2d(weights, values, costs, W, V):
    n = len(weights)
    dp = [[[0] * (V + 1) for _ in range(W + 1)] for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(W + 1):
            for k in range(V + 1):
                dp[i][j][k] = dp[i-1][j][k]
                if j >= weights[i-1] and k >= costs[i-1]:
                    dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-weights[i-1]][k-costs[i-1]] + values[i-1])
    return dp[n][W][V]

分组背包问题

问题描述：

每个物品属于一个组，每组中最多选择一个物品放入背包。

解法：

使用二维数组dp[i][j] 表示前 \( i \) 组物品在容量为 \( j \) 时的最大价值，状态转移方程为：

\[ dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_{i,k}] + v_{i,k}) \]

def knapsack_group(groups, W):
    n = len(groups)
    dp = [0] * (W + 1)
    for group in groups:
        for j in range(W, -1, -1):
            for item in group:
                if j >= item['weight']:
                    dp[j] = max(dp[j], dp[j - item['weight']] + item['value'])
    return dp[W]

有依赖的背包问题

问题描述：

每个物品有一个依赖关系，只有当其依赖的物品被放入背包后，该物品才能被放入背包。

解法：

使用树形结构表示依赖关系，先处理没有依赖的物品，再逐层处理依赖的物品。

from collections import defaultdict
def knapsack_dependent(items, dependencies, W):
    graph = defaultdict(list)
    indegree = {item: 0 for item in items}
    for u, v in dependencies:
        graph[u].append(v)
        indegree[v] += 1
    
    queue = [item for item in items if indegree[item] == 0]
    dp = [0] * (W + 1)
    while queue:
        next_queue = []
        for item in queue:
            weight, value = items[item]['weight'], items[item]['value']
            for j in range(W, weight - 1, -1):
                dp[j] = max(dp[j], dp[j - weight] + value)
            for neighbor in graph[item]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    next_queue.append(neighbor)
        queue = next_queue
    return dp[W]

树形背包问题

问题描述：

物品之间有树形依赖关系，每个节点可以包含多个子节点，每个子节点的物品可以选择是否放入背包。

解法：

使用深度优先搜索（DFS）遍历树，计算每个节点的最优解。

def dfs(node, parent, weights, values, children, W, memo):
    if (node, W) in memo:
        return memo[(node, W)]
    
    dp = [0] * (W + 1)