背包问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

  动态规划的本质：它是一种 “以空间换时间”的优化算法，核心是把复杂问题拆解为多个重叠的子问题，通过记录子问题的最优解（状态），避免重复计算，最终由子问题的最优解推导出原问题的最优解。

算法回顾

• 动态规划的适用有三个核心前提（缺一不可），这也是判断一个问题是否能用 DP 解决的关键：
  • 最优子结构：原问题的最优解包含其子问题的最优解；
  • 重叠子问题：求解原问题时，会反复遇到相同的子问题（这是 DP 能优化的基础，否则不如暴力递归）；
  • 无后效性：某一阶段的状态确定后，后续的状态推导只依赖当前状态，与状态的形成过程无关。

背包问题

  背包问题是动态规划的经典专项，属于带约束的最值 / 计数问题，核心场景是 “在有限的容量约束下，选择物品使价值最大 / 数量最多，或求合法选择的方案数”。根据物品的选择规则，分为三大经典类型，解题思路高度统一，是 DP 的必学专项。

背包类型	核心规则	典型问题	状态定义（二维）
01 背包	每个物品只能选一次	选物品使总价值最大（容量有限）	dp[i][j]：前 i 个物品，容量 j 的最大价值
完全背包	每个物品可以选无限次	组合总和 IV（LeetCode 377）	dp[i][j]：前 i 个物品，和为 j 的方案数
多重背包	每个物品选择有次数限制	选物品（有数量限制）使价值最大	dp[i][j]：前 i 个物品，容量 j 的最大价值

• 核心解题思路
  
  • 定义状态：dp[i][j] 表示 前 i 个物品，容量 j 的最大价值；
  • 初始状态：dp[0][j] = 0（无物品，价值为 0）、dp[i][0] = 0（无容量，价值为 0）；
  • 状态转移：对每个物品，选或不选：
    • 不选（容量不够）：
      • dp[i][j] = 前 i-1 个物品在容量 j 下的最大价值
      • dp[i][j] = dp[i-1][j]
    • 选（容量足够）：
      • dp[i][j] = max(前 i-1 个物品在容量 j 下的最大价值, 前 i-1 个物品在容量 j-w[i-1] 下的价值 + 当前物品 v[i-1] 价值)
      • dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])（w 为物品重量，v 为价值）
  • 遍历顺序：从左到右（i 从 1 到 n 对应第i个物品，j 从 1 到 c 对应 j 容量）。
  • 最终 dp[n-1][c-1] 就是最大价值。

• 典型例题
  • 01 背包（基础）：有限容量选物品（各一次），价值最大；
  • 零钱兑换（LeetCode 322）：完全背包的最值型问题（最少硬币数凑成目标金额）；
  • 零钱兑换 II（LeetCode 518）：完全背包的计数型问题（凑成目标金额的硬币组合数）。

一、01 背包

问题描述：

• 有 n 件物品和一个最多能装重量为 c 的背包。第 i 件物品的重量是 w[i] ，得到的价值是 v[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
• 提示：
  • 1 <= n <= 10，1 <= c <= 100
  • w[0...n-1]，v[0...n-1]
• 示例 1：
  • 输入：
    • n = 4, c = 8
    • w = [1,2,3,4]，v = [5,6,7,8]
  • 输出：20

算法解析：

1. 定义状态：dp[i][j] 表示 前 i 个物品，容量 j 的最大价值；
2. 初始状态：dp[0][j] = 0（无物品，价值为 0）、dp[i][0] = 0（无容量，价值为 0）；
3. 状态转移：对每个物品，选或不选：
   • 不选（容量不够）：
     • dp[i][j] = 前 i-1 个物品在容量 j 下的最大价值
     • dp[i][j] = dp[i-1][j]
   • 选（容量足够）：
     • dp[i][j] = max(前 i-1 个物品在容量 j 下的最大价值, 前 i-1 个物品在容量 j-w[i-1] 下的价值 + 当前物品 v[i-1] 价值)
     • dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1])（w 为物品重量，v 为价值）
4. 遍历顺序：从左到右（i 从 1 到 n 对应第i个物品，j 从 1 到 c 对应 j 容量）。
5. 最终 dp[n-1][c-1] 就是最大价值。

dp 数组计算过程：

输入：

• n = 4, c = 8, w = [1,2,3,4], v = [5,6,7,8]

1. 初始化 DP 数组：全部为 0
2. 填充最大价值：
   
   • i=1
     • j=1： dp[i][j] = max( dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max( 0 , 0 + 5) = 5 单击演示
     • j=2：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=3：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=4：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=5：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=6：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=7：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
     • j=8：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(0 , 0 + 5) = 5 单击演示
   • i=2
     
     • j=1： dp[i][j] = dp[i-1][j] = 5 单击演示
     • j=2：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 0 + 6) = 6 单击演示
     • j=3：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
     • j=4：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
     • j=5：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
     • j=6：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
     • j=7：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
     • j=8：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(5 , 5 + 6) = 11 单击演示
   • i=3
     
     • j=1： dp[i][j] = dp[i-1][j] = 5 单击演示
     • j=2： dp[i][j] = dp[i-1][j] = 6 单击演示
     • j=3：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 0 + 7) = 11 单击演示
     • j=4：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 5 + 7) = 12 单击演示
     • j=5：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 6 + 7) = 13 单击演示
     • j=6：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 11 + 7) = 18 单击演示
     • j=7：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 11 + 7) = 18 单击演示
     • j=8：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(11 , 11 + 7) = 18 单击演示
   • i=4
     
     • j=1： dp[i][j] = dp[i-1][j] = 5 单击演示
     • j=2： dp[i][j] = dp[i-1][j] = 6 单击演示
     • j=2： dp[i][j] = dp[i-1][j] = 11 单击演示
     • j=4：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(12 , 0 + 8) = 12 单击演示
     • j=5：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(13 , 5 + 8) = 13 单击演示
     • j=6：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(18 , 6 + 8) = 18 单击演示
     • j=7：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(18 , 11 + 8) = 19 单击演示
     • j=8：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]) = max(18 , 12 + 8) = 20 单击演示

#include <iostream>
#include <vector>
using namespace std;

int zeroOneKnapsack(int C, vector<int>& w, vector<int>& v) {
    int n = w.size();
    // 二维DP数组：dp[i][j] 前i个物品，容量j的最大价值
    vector<vector<int>> dp(n + 1, vector<int>(C + 1, 0));

    // 遍历每个物品（i从1到n，对应第i个物品）
    for (int i = 1; i <= n; ++i) {
        // 遍历所有可能的背包容量
        for (int j = 1; j <= C; ++j) {
            // 容量不足，无法选第i个物品
            if (j < w[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                // 容量足够，选或不选取最大值
                dp[i][j] = max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);
            }
        }
    }

    // 输出DP数组（可选，帮助理解）
    cout << "DP数组（行：物品数，列：容量）：" << endl;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= C; ++j) {
            printf("%3d",dp[i][j]);
        }
        cout << endl;
    }

    return dp[n][C];
}

int main() {
    // 示例：背包容量C=8，物品重量[1,2,3,4]，价值[5,6,7,8]
    int C = 8;
    vector<int> w = {1, 2, 3, 4};
    vector<int> v = {5, 6, 7, 8};

    int maxValue = zeroOneKnapsack(C, w, v);
    cout << "背包最大价值：" << maxValue << endl; 

    return 0;
} 
        

输出结果

  DP数组（行：物品数，列：容量）：
  0  0  0  0  0  0  0  0  0
  0  5  5  5  5  5  5  5  5
  0  5  6 11 11 11 11 11 11
  0  5  6 11 12 13 18 18 18
  0  5  6 11 12 13 18 19 20
背包最大价值：20
        

二、零钱兑换（LeetCode 322）

问题描述：

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
  • 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
  • 你可以认为每种硬币的数量是无限的。
• 提示:
  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2³¹ - 1
  • 0 <= amount <= 10⁴
• 示例 1：
  • 输入：coins = [1, 2, 5], amount = 11
  • 输出：3
  • 解释：11 = 5 + 5 + 1
• 示例 2：
  • 输入：coins = [2], amount = 3
  • 输出：-1
• 示例 3：
  • 输入：coins = [1], amount = 0
  • 输出：0

算法解析：

1. 定义状态：dp[i] 表示凑成金额 i 所需的最少硬币数。
2. 初始状态：
   • dp[0] = 0（凑成金额 0 不需要任何硬币）；
   • 其他 dp[i] 初始化为一个较大的值（比如 amount + 1），表示初始时无法凑成该金额。
3. 状态转移：
   • 对于每个金额 i（从 1 到 amount），遍历所有硬币面额 coin，如果 coin <= i，则 dp[i] = min(dp[i], dp[i - coin] + 1)（即凑成 i 的最少硬币数 = 凑成 i - coin 的最少硬币数 + 1 枚当前硬币）。
4. 遍历顺序：从左到右（i 从 1 到 amount 目标金额，遍历每种硬币面额）。
5. 如果最终 dp[amount] 仍大于 amount，说明无法凑成，返回 -1；否则返回 dp[amount]。

#include <iostream>
#include <vector>
#include <climits> // 用于 INT_MAX
#include <algorithm> // 用于 min 函数

using namespace std;

int coinChange(vector<int>& coins, int amount) {
    // 定义dp数组，dp[i]表示凑成金额i所需的最少硬币数
    // 初始化大小为amount+1，值为一个极大值（表示初始不可达）
    vector<int> dp(amount + 1, INT_MAX);
    // 基准条件：凑成0元需要0枚硬币
    dp[0] = 0;

    // 遍历每个金额，从1到目标金额
    for (int i = 1; i <= amount; ++i) {
        // 遍历每种硬币面额
        for (int coin : coins) {
            // 条件1：当前硬币面额不超过当前金额
            // 条件2：dp[i - coin]不是初始的极大值（说明i - coin金额是可达的）
            if (coin <= i && dp[i - coin] != INT_MAX) {
                // 状态转移：取当前dp[i]和「凑i-coin的硬币数+1」的最小值
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    // 如果dp[amount]还是极大值，说明无法凑成，返回-1；否则返回结果
    return dp[amount] == INT_MAX ? -1 : dp[amount];
}

int main() {
    // 测试用例1：[1,2,5] 凑11元，预期输出3
    vector<int> coins1 = {1, 2, 5};
    cout << coinChange(coins1, 11) << endl;

    // 测试用例2：[2] 凑3元，预期输出-1
    vector<int> coins2 = {2};
    cout << coinChange(coins2, 3) << endl;

    // 测试用例3：[1] 凑0元，预期输出0
    vector<int> coins3 = {1};
    cout << coinChange(coins3, 0) << endl;

    return 0;
}
        

输出结果

3
-1
0
            

三、零钱兑换 II（LeetCode 518）

问题描述：

• 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
  • 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
  • 假设每一种面额的硬币有无限个。
  • 题目数据保证结果符合 32 位带符号整数。
• 提示:
  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000
• 示例 1：
  • 输入：amount = 5, coins = [1, 2, 5]
  • 输出：4
  • 解释：有四种方式可以凑成总金额：
    • 5=5
    • 5=2+2+1
    • 5=2+1+1+1
    • 5=1+1+1+1+1
• 示例 2：
  • 输入：amount = 3, coins = [2]
  • 输出：0
  • 解释：只用面额 2 的硬币不能凑成总金额 3 。
• 示例 3：
  • 输入：amount = 10, coins = [10]
  • 输出：1

算法解析：

1. 定义状态：dp[i] 表示凑成金额 i 的组合总数。
2. 初始状态：
   • dp[0] = 1（凑成金额 0 只有 1 种方式：不选任何硬币）；
   • 其余 dp[i] = 0。。
3. 状态转移：
   • 先遍历硬币（保证组合不考虑顺序），再遍历金额（从硬币面额到目标金额）；
   • 对于每个硬币 coin 和金额 i（i >= coin），dp[i] += dp[i - coin]（即凑成 i 的组合数 = 原有组合数 + 加入当前硬币后新增的组合数）。
4. 遍历顺序：遍历每一种硬币，遍历金额，从coin到amount。
5. 最终 dp[amount] 就是所求的组合总数。

#include <iostream>
#include <vector>

using namespace std;

int change(int amount, vector<int>& coins) {
    // 初始化dp数组，dp[i]表示凑成金额i的组合数
    vector<int> dp(amount + 1, 0);
    // 基准条件：凑成0元只有1种方式（不选任何硬币）
    dp[0] = 1;

    // 第一步：遍历每一种硬币（先遍历硬币保证组合不考虑顺序）
    for (int coin : coins) {
        // 第二步：遍历金额，从coin到amount（完全背包：物品可重复选，正序遍历）
        for (int i = coin; i <= amount; ++i) {
            // 状态转移：累加「不使用当前硬币的组合数」和「使用当前硬币的组合数」
            dp[i] += dp[i - coin];
        }
    }

    // dp[amount]即为凑成目标金额的组合总数
    return dp[amount];
}

int main() {
    // 测试用例1：amount=5, coins=[1,2,5]，预期输出4（5；2+2+1；2+1+1+1；1*5）
    vector<int> coins1 = {1, 2, 5};
    cout << change(5, coins1) << endl;

    // 测试用例2：amount=3, coins=[2]，预期输出0（无法凑成）
    vector<int> coins2 = {2};
    cout << change(3, coins2) << endl;

    // 测试用例3：amount=0, coins=[1]，预期输出1（空组合）
    vector<int> coins3 = {1};
    cout << change(0, coins3) << endl;

    return 0;
}
        

输出结果

4
0
1