08-背包问题

💡 核心结论

背包问题本质

  • 定义：在容量限制下，选择物品使价值最大

  • 核心：动态规划的经典应用

  • 关键：每个物品选或不选，累积最优解

  • 难点：状态定义、空间优化

  • 应用：资源分配、项目选择、切割问题

三种背包对比

类型

特点

状态转移

遍历顺序

0-1背包

每个物品最多1个

max(不选, 选)

逆序

完全背包

每个物品无限个

max(不选, 选)

正序

多重背包

每个物品k个

二进制优化

-

0-1背包核心

状态：dp[i][j] = 前i个物品，容量j的最大价值
转移：dp[i][j] = max(
    dp[i-1][j],              # 不选第i个
    dp[i-1][j-w[i]] + v[i]   # 选第i个
)
空间优化：一维数组，逆序遍历

完全背包核心

状态：dp[i][j] = 前i种物品，容量j的最大价值  
转移：dp[i][j] = max(
    dp[i-1][j],          # 不选第i种
    dp[i][j-w[i]] + v[i] # 选第i种（注意是dp[i]不是dp[i-1]）
)
空间优化：一维数组，正序遍历

🎯 0-1背包

二维DP

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

一维DP（空间优化）

def knapsack_01_optimized(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # 逆序遍历（避免物品被重复选择）
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

🔄 完全背包

一维DP

def knapsack_complete(weights, values, capacity):
    dp = [0] * (capacity + 1)
    
    for i in range(len(weights)):
        # 正序遍历（允许物品被重复选择）
        for j in range(weights[i], capacity + 1):
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
    
    return dp[capacity]

🎁 多重背包

二进制优化

def knapsack_multiple(weights, values, counts, capacity):
    # 转换为0-1背包
    new_weights = []
    new_values = []
    
    for i in range(len(weights)):
        k = 1
        while k <= counts[i]:
            new_weights.append(weights[i] * k)
            new_values.append(values[i] * k)
            counts[i] -= k
            k *= 2
        if counts[i] > 0:
            new_weights.append(weights[i] * counts[i])
            new_values.append(values[i] * counts[i])
    
    return knapsack_01_optimized(new_weights, new_values, capacity)

🎯 背包变种

1. 恰好装满

# 初始化
dp = [-inf] * (capacity + 1)
dp[0] = 0  # 容量0价值0

2. 求方案数

# 状态：dp[i] = 容量i的方案数
dp[j] += dp[j - weight[i]]  # 累加方案数

3. 求具体方案

# 记录选择
choice = [[False] * (capacity + 1) for _ in range(n + 1)]

# 回溯方案
result = []
j = capacity
for i in range(n, 0, -1):
    if choice[i][j]:
        result.append(i - 1)
        j -= weights[i - 1]

📚 LeetCode练习

0-1背包

完全背包

💡 解题模板

0-1背包模板

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

完全背包模板

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

🎯 关键区别

0-1背包 vs 完全背包唯一区别：

  • 0-1：for j in range(capacity, w-1, -1) 逆序

  • 完全：for j in range(w, capacity+1) 正序

为什么？

  • 逆序：保证每个物品只用一次

  • 正序：允许物品重复使用

💻 完整代码实现

Python 实现

  1"""
  2背包问题实现
  3"""
  4
  5# ========== 0-1背包 ==========
  6
  7def knapsack_01(weights, values, capacity):
  8    """0-1背包（二维DP）"""
  9    n = len(weights)
 10    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
 11    
 12    for i in range(1, n + 1):
 13        for j in range(capacity + 1):
 14            if j < weights[i-1]:
 15                dp[i][j] = dp[i-1][j]
 16            else:
 17                dp[i][j] = max(
 18                    dp[i-1][j],
 19                    dp[i-1][j - weights[i-1]] + values[i-1]
 20                )
 21    
 22    return dp[n][capacity]
 23
 24
 25def knapsack_01_optimized(weights, values, capacity):
 26    """0-1背包（一维DP优化）"""
 27    dp = [0] * (capacity + 1)
 28    
 29    for i in range(len(weights)):
 30        # 逆序遍历
 31        for j in range(capacity, weights[i] - 1, -1):
 32            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
 33    
 34    return dp[capacity]
 35
 36
 37# ========== 完全背包 ==========
 38
 39def knapsack_complete(weights, values, capacity):
 40    """完全背包（物品可重复选择）"""
 41    dp = [0] * (capacity + 1)
 42    
 43    for i in range(len(weights)):
 44        # 正序遍历
 45        for j in range(weights[i], capacity + 1):
 46            dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
 47    
 48    return dp[capacity]
 49
 50
 51# ========== 多重背包 ==========
 52
 53def knapsack_multiple(weights, values, counts, capacity):
 54    """多重背包（每个物品有数量限制）"""
 55    # 二进制优化：转换为0-1背包
 56    new_weights = []
 57    new_values = []
 58    
 59    for i in range(len(weights)):
 60        count = counts[i]
 61        k = 1
 62        while k <= count:
 63            new_weights.append(weights[i] * k)
 64            new_values.append(values[i] * k)
 65            count -= k
 66            k *= 2
 67        if count > 0:
 68            new_weights.append(weights[i] * count)
 69            new_values.append(values[i] * count)
 70    
 71    return knapsack_01_optimized(new_weights, new_values, capacity)
 72
 73
 74# ========== 应用：分割等和子集 ==========
 75
 76def can_partition(nums):
 77    """判断能否分割成两个和相等的子集"""
 78    total = sum(nums)
 79    if total % 2:
 80        return False
 81    
 82    target = total // 2
 83    dp = [False] * (target + 1)
 84    dp[0] = True
 85    
 86    for num in nums:
 87        for j in range(target, num - 1, -1):
 88            dp[j] = dp[j] or dp[j - num]
 89    
 90    return dp[target]
 91
 92
 93# ========== 应用：零钱兑换 ==========
 94
 95def coin_change(coins, amount):
 96    """最少硬币数（完全背包）"""
 97    dp = [float('inf')] * (amount + 1)
 98    dp[0] = 0
 99    
100    for coin in coins:
101        for j in range(coin, amount + 1):
102            dp[j] = min(dp[j], dp[j - coin] + 1)
103    
104    return dp[amount] if dp[amount] != float('inf') else -1
105
106
107def coin_change_ways(coins, amount):
108    """组成金额的方案数（完全背包）"""
109    dp = [0] * (amount + 1)
110    dp[0] = 1
111    
112    for coin in coins:
113        for j in range(coin, amount + 1):
114            dp[j] += dp[j - coin]
115    
116    return dp[amount]
117
118
119def demo():
120    """演示背包问题"""
121    print("=== 背包问题演示 ===\n")
122    
123    # 0-1背包
124    weights = [2, 3, 4, 5]
125    values = [3, 4, 5, 6]
126    capacity = 8
127    
128    print(f"0-1背包:")
129    print(f"  重量: {weights}")
130    print(f"  价值: {values}")
131    print(f"  容量: {capacity}")
132    print(f"  最大价值: {knapsack_01(weights, values, capacity)}")
133    print(f"  最大价值（优化）: {knapsack_01_optimized(weights, values, capacity)}\n")
134    
135    # 完全背包
136    print(f"完全背包:")
137    print(f"  最大价值: {knapsack_complete(weights, values, capacity)}\n")
138    
139    # 多重背包
140    counts = [1, 2, 3, 1]
141    print(f"多重背包:")
142    print(f"  数量: {counts}")
143    print(f"  最大价值: {knapsack_multiple(weights, values, counts, capacity)}\n")
144    
145    # 分割等和子集
146    nums = [1, 5, 11, 5]
147    print(f"分割等和子集 {nums}:")
148    print(f"  能否分割: {can_partition(nums)}\n")
149    
150    # 零钱兑换
151    coins, amount = [1, 2, 5], 11
152    print(f"零钱兑换:")
153    print(f"  硬币: {coins}, 金额: {amount}")
154    print(f"  最少硬币数: {coin_change(coins, amount)}")
155    print(f"  方案数: {coin_change_ways(coins, amount)}")
156
157
158if __name__ == '__main__':
159    demo()
160

C++ 实现

  1/**
  2 * 背包问题实现
  3 */
  4
  5#include <iostream>
  6#include <vector>
  7#include <algorithm>
  8
  9using namespace std;
 10
 11// 0-1背包（二维DP）
 12int knapsack01(const vector<int>& weights, const vector<int>& values, int capacity) {
 13    int n = weights.size();
 14    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
 15    
 16    for (int i = 1; i <= n; i++) {
 17        for (int j = 0; j <= capacity; j++) {
 18            if (j < weights[i-1]) {
 19                dp[i][j] = dp[i-1][j];
 20            } else {
 21                dp[i][j] = max(
 22                    dp[i-1][j],
 23                    dp[i-1][j - weights[i-1]] + values[i-1]
 24                );
 25            }
 26        }
 27    }
 28    
 29    return dp[n][capacity];
 30}
 31
 32// 0-1背包（一维优化）
 33int knapsack01Optimized(const vector<int>& weights, const vector<int>& values, int capacity) {
 34    vector<int> dp(capacity + 1, 0);
 35    
 36    for (int i = 0; i < weights.size(); i++) {
 37        // 逆序遍历
 38        for (int j = capacity; j >= weights[i]; j--) {
 39            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
 40        }
 41    }
 42    
 43    return dp[capacity];
 44}
 45
 46// 完全背包
 47int knapsackComplete(const vector<int>& weights, const vector<int>& values, int capacity) {
 48    vector<int> dp(capacity + 1, 0);
 49    
 50    for (int i = 0; i < weights.size(); i++) {
 51        // 正序遍历
 52        for (int j = weights[i]; j <= capacity; j++) {
 53            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
 54        }
 55    }
 56    
 57    return dp[capacity];
 58}
 59
 60// 零钱兑换（完全背包）
 61int coinChange(const vector<int>& coins, int amount) {
 62    vector<int> dp(amount + 1, INT_MAX);
 63    dp[0] = 0;
 64    
 65    for (int coin : coins) {
 66        for (int j = coin; j <= amount; j++) {
 67            if (dp[j - coin] != INT_MAX) {
 68                dp[j] = min(dp[j], dp[j - coin] + 1);
 69            }
 70        }
 71    }
 72    
 73    return dp[amount] == INT_MAX ? -1 : dp[amount];
 74}
 75
 76// 零钱兑换II（方案数）
 77int coinChangeWays(const vector<int>& coins, int amount) {
 78    vector<int> dp(amount + 1, 0);
 79    dp[0] = 1;
 80    
 81    for (int coin : coins) {
 82        for (int j = coin; j <= amount; j++) {
 83            dp[j] += dp[j - coin];
 84        }
 85    }
 86    
 87    return dp[amount];
 88}
 89
 90// 分割等和子集
 91bool canPartition(const vector<int>& nums) {
 92    int sum = 0;
 93    for (int num : nums) sum += num;
 94    
 95    if (sum % 2) return false;
 96    
 97    int target = sum / 2;
 98    vector<bool> dp(target + 1, false);
 99    dp[0] = true;
100    
101    for (int num : nums) {
102        for (int j = target; j >= num; j--) {
103            dp[j] = dp[j] || dp[j - num];
104        }
105    }
106    
107    return dp[target];
108}
109
110int main() {
111    cout << "=== 背包问题演示 ===" << endl << endl;
112    
113    // 0-1背包
114    vector<int> weights = {2, 3, 4, 5};
115    vector<int> values = {3, 4, 5, 6};
116    int capacity = 8;
117    
118    cout << "0-1背包:" << endl;
119    cout << "  重量: [2,3,4,5]" << endl;
120    cout << "  价值: [3,4,5,6]" << endl;
121    cout << "  容量: 8" << endl;
122    cout << "  最大价值: " << knapsack01(weights, values, capacity) << endl;
123    cout << "  最大价值（优化）: " << knapsack01Optimized(weights, values, capacity) << endl << endl;
124    
125    // 完全背包
126    cout << "完全背包:" << endl;
127    cout << "  最大价值: " << knapsackComplete(weights, values, capacity) << endl << endl;
128    
129    // 零钱兑换
130    vector<int> coins = {1, 2, 5};
131    int amount = 11;
132    cout << "零钱兑换:" << endl;
133    cout << "  硬币: [1,2,5], 金额: 11" << endl;
134    cout << "  最少硬币数: " << coinChange(coins, amount) << endl;
135    cout << "  方案数: " << coinChangeWays(coins, amount) << endl << endl;
136    
137    // 分割等和子集
138    vector<int> nums = {1, 5, 11, 5};
139    cout << "分割等和子集 [1,5,11,5]:" << endl;
140    cout << "  能否分割: " << (canPartition(nums) ? "是" : "否") << endl;
141    
142    return 0;
143}