【C语言】动态规划---01背包/完全背包

南瓜(≧∇≦)

347人浏览 · 2026-03-22 13:27:41

南瓜(≧∇≦) · 2026-03-22 13:27:41 发布

文章目录

从零到一彻底搞懂 0-1 背包与完全背包
例题解析
总结

从零到一彻底搞懂 0-1 背包与完全背包

背包问题是动态规划的经典入门题，核心分为 0-1 背包（物品只能选一次）和 完全背包（物品可以选无限次）。本文将从最直观的二维动态规划讲起，再逐步优化到一维滚动数组，配合具体例子和表格，让你彻底理解背后的逻辑。

0-1 背包问题

问题定义

有 n 个物品，每个物品只能选一次，第i个物品的重量为 w[i]，价值为 v[i]；背包的总容量为 C。求在不超过背包容量的前提下，能装入的最大价值。

示例：

物品数量 n = 3，背包容量 C = 4
重量数组 w = [1, 2, 3]
价值数组 v = [15, 20, 30]

二维动态规划（最直观）

状态定义

我们定义 dp[i][j] 表示：前 i 个物品，在背包容量为 j 时，能获得的最大价值。

状态转移方程

对于第 i 个物品，我们有两种选择：

不选第 i 个物品：最大价值就是前 i - 1 个物品在容量 j 时的价值，即 dp[i-1][j]；
选第 i 个物品：前提是 j >= w[i]（容量够装），此时最大价值是 “前 i - 1 个物品在容量 j - w[i] 时的价值” 加上当前物品的价值，即 dp[i-1][j - w[i]] + v[i]。

我们用上面的示例来填充 dp 表格（行是物品 i，列是容量 j）

物品 \ 容量	1	2	3	4
0（无物品）	0	0	0	0
1（w=1,v=15）	15	15	15	15
2（w=2,v=20）	15	20	35	35
3（w=3,v=30）	15	20	30	45

填充过程详解：

第 0 行（无物品）所有容量的价值都是 0。
第 1 行（物品 1，w=1，v=15）
- j=0：装不下，价值 0；
- j>=1：选物品 1，价值 15（不选的话是 0，选更大）。
第 2 行（物品 2，w=2，v=20）
- j=0：0；
- j=1：装不下物品 2，所以继承第 1 行的 15；
- j=2：不选是 15，选是dp[1][0]+20=20，取 20；
- j=3：不选是 15，选是dp[1][1]+20=15+20=35，取 35；
- j=4：不选是 15，选是dp[1][2]+20=15+20=35，取 35。
第 3 行（物品 3，w=3，v=30）
- j=0-2：装不下，继承第 2 行；
- j=3：不选是 20，选是dp[2][0]+30=30，取 30；
- j=4：不选是 35，选是dp[2][1]+30=15+30=45，取 45。

最终答案就是 dp[3][4] = 45。

一维滚动数组优化（空间从 $O (n C)$ → $O (C)$ ）

优化原理

观察二维状态转移方程，你会发现：dp[i][j] 只依赖上一行（i-1 行）的 dp[i-1][j] 和 dp[i-1][j-w[i]]。也就是说，我们不需要保存整个二维数组，只需要保存 “上一行” 的状态即可，因此可以用一维数组 dp[j] 来替代。

状态转移方程（一维）

$d p [j] = ma x (d p [j], d p [j - w [i]] + v [i])$

dp[j]：不选第 i 个物品时的价值（继承上一轮的结果）；
dp[j - w[i]] + v[i]：选第 i 个物品时的价值。

关键：倒序遍历容量！
这是 0-1 背包一维优化的核心：必须从大到小倒序遍历容量 j（从 C 到 w[i]）。
为什么要倒序？如果正序遍历，dp[j - w[i]] 会被当前轮次更新过的值覆盖，导致同一个物品被选多次（就变成完全背包了）。倒序可以保证 dp[j - w[i]] 是上一轮（i-1 行）的旧值，对应 “物品只能选一次”。

完全背包问题

问题定义

和 0-1 背包的唯一区别：每个物品可以选无限次，其他条件不变。
示例（和 0-1 背包一样）：
n=3，C=4，w=[1,2,3]，v=[15,20,30]

二维动态规划

状态定义

和 0-1 背包完全一致：dp[i][j] 表示前 i 个物品，容量 j 时的最大价值。

状态转移方程（核心区别）

因为物品可以选无限次，所以选了第 i 个物品后，还可以继续选第 i 个。因此：
不选第 i 个物品：dp[i-1][j]（和 0-1 一样）；
选第 i 个物品：dp[i][j - w[i]] + v[i]（注意是 dp[i] 而不是 dp[i-1]，表示可以重复选当前物品）。

物品 \ 容量	1	2	3	4
0（无物品）	0	0	0	0
1（w=1,v=15）	15	30	45	60
2（w=2,v=20）	15	30	45	60
3（w=3,v=30）	15	30	45	60

填充过程详解：

第 1 行（物品 1，w=1，v=15）
- 因为可以无限选，所以 j=1 选 1 个（15），j=2 选 2 个（30），j=3 选 3 个（45），j=4 选 4 个（60）。
第 2 行（物品 2，w=2，v=20）
- j=4：不选是 60，选是dp[2][2]+20=30+20=50，取 60（还是选 4 个物品 1 更优）。
第 3 行（物品 3，w=3，v=30）
- 同理，最优解还是选 4 个物品 1，价值 60。

最终答案 dp[3][4] = 60。

一维滚动数组优化

状态转移方程

和 0-1 背包的一维方程完全一样：
$d p [j] = ma x (d p [j], d p [j - w [i]] + v [i])$

关键：正序遍历容量！
这是完全背包和 0-1 背包的核心区别：完全背包需要从小到大正序遍历容量 j（从 w[i] 到 C）。

为什么要正序？
正序遍历时，dp[j - w[i]] 会被当前轮次更新过的值覆盖，这正好对应 “物品可以选无限次”（因为我们可以在当前轮次重复选同一个物品）。

0-1 背包与完全背包核心对比

维度	0-1 背包	完全背包
物品选择次数	只能选一次	可以选无限次
二维状态转移（选物品时）	`dp[i-1][j-w[i]] + v[i]`	`dp[i][j-w[i]] + v[i]`
一维遍历顺序	倒序（C→w [i]）	正序（w [i]→C）
一维核心逻辑	保证用的是 “上一轮的旧值”（不重复选）	允许用 “当前轮的新值”（重复选）

例题解析

原题链接
279. 完全平方数 - 力扣（LeetCode）

读完此题我们可以发现，其实这道题就是换皮的完全背包问题，我们把这道题的每个元素，和完全背包的定义一一对应：

完全背包要素	本题对应内容
背包总容量	目标和 `n`
物品列表	所有 ≤n 的完全平方数（1、4、9、16…）
物品重量	完全平方数本身的值（比如物品 4 的重量是 4）
物品价值	固定为 1（我们要统计「个数」，每个物品贡献 1 个数量）
物品选择规则	可无限次选取（完全平方数可重复使用）
问题目标	凑满背包容量的前提下，最小化总价值（最少个数）

接下来我们就着手于本题动态规划思路的解析：

状态定义
dp[i]：凑出和为 i 的完全平方数的最少数量。
状态转移方程
对于每个完全平方数 num，如果 num ≤ i，我们可以选择选这个数，那么：
dp[i]=min(dp[i], dp[i−num]+1)
dp[i]：不选当前num时的最少数量
dp[i - num] + 1：选当前num时的最少数量（i-num的最少数量 + 当前 1 个）
初始化
dp[0] = 0：凑出和为 0，需要 0 个平方数（基准条件）
其他dp[i]初始化为一个足够大的数（比如i + 1，因为最多用 i 个 1，不可能超过这个数），避免初始值干扰最小值的计算。
遍历顺序
因为是完全背包（物品可无限选），所以我们对背包容量要正序遍历；
先遍历物品（所有完全平方数），再正序遍历背包容量（从num到n）。
最终结果
dp[n] 就是凑出和为 n 的最少完全平方数数量。

代码如下：

int numSquares(int n) {
    // 1. 初始化dp数组
    int* dp = (int*)malloc(sizeof(int) * (n + 1));
    // 初始化为足够大的数（最多n个1，所以n+1一定比最大可能值大）
    for (int i = 0; i <= n; i++) {
        dp[i] = n + 1;
    }
    dp[0] = 0; // 基准条件

    // 2. 遍历所有物品（完全平方数）
    int maxK = sqrt(n); // 最大的k，满足k²≤n
    for (int k = 1; k <= maxK; k++) {
        int num = k * k; // 当前物品（完全平方数）
        // 3. 正序遍历背包容量（完全背包规则）
        for (int j = num; j <= n; j++) {
            dp[j] = fmin(dp[j], dp[j - num] + 1);
        }
    }

    int res = dp[n];
    return res;
}

原题链接
322. 零钱兑换 - 力扣（LeetCode）

这道题依旧是完全背包的问题，这里给出对应关系：

完全背包核心要素	本题对应内容
背包总容量	目标总金额 `amount`
物品列表	不同面额的硬币 `coins`
物品重量	硬币的面额（比如硬币 5 的重量是 5）
物品价值	固定为 1（我们要统计硬币个数，每个硬币贡献 1 个数量）
物品选择规则	可无限次选取（硬币数量无限，对应完全背包）
问题目标	凑满背包容量的前提下，最小化总价值（最少硬币个数）

状态定义

dp[j]：凑出金额j所需的最少硬币个数。

状态转移方程

对于每一个硬币coin，如果coin ≤ j（硬币面额不超过当前金额），我们可以选择使用这个硬币，那么：

dp[j]=min(dp[j], dp[j−coin]+1)

dp[j]：不选当前硬币时的最少硬币数（继承之前的结果）
dp[j - coin] + 1：选当前硬币时的最少硬币数（凑出j-coin的最少个数 + 当前 1 个硬币）

初始化

dp[0] = 0：凑出金额 0 需要 0 个硬币，这是递推的基准条件
其他dp[j]初始化为一个足够大的数：这里我们用amount + 1，因为凑出amount最多需要amount个 1 元硬币，amount + 1是一个不可能达到的大数，用来表示「无法凑出」，避免初始值干扰最小值的计算。

遍历顺序（完全背包核心规则）

因为硬币可以无限选，属于完全背包，所以对「背包容量（金额）」要正序遍历（和 01 背包的倒序遍历完全相反）。

外层遍历物品（所有硬币）
内层正序遍历背包容量（从coin到amount）

补充：完全背包中，先遍历物品还是先遍历容量，对最终结果没有影响，先遍历物品更符合我们的思维习惯。

最终结果

如果dp[amount] > amount（还是初始的大数），说明无法凑出，返回-1
否则返回dp[amount]，就是最少硬币个数

代码如下：

int coinChange(int* coins, int coinsSize, int amount) {
    // 1. 初始化dp数组
    int* dp = (int*)malloc(sizeof(int) * (amount + 1));
    // 初始化为amount+1（不可能达到的大数）
    for (int j = 0; j <= amount; j++) {
        dp[j] = amount + 1;
    }
    dp[0] = 0; // 基准条件：金额0需要0个硬币

    // 2. 遍历所有物品（硬币）
    for (int i = 0; i < coinsSize; i++) {
        int coin = coins[i];
        // 3. 正序遍历背包容量（完全背包规则）
        for (int j = coin; j <= amount; j++) {
            dp[j] = fmin(dp[j], dp[j - coin] + 1);
        }
    }

    // 4. 处理结果：如果还是大数，说明无法凑出，返回-1
    int res = dp[amount] > amount ? -1 : dp[amount];
    free(dp);
    return res;
}

总结

二维 DP 基础版（通用理解）

背包类型	状态定义	状态转移方程
0-1 背包	`dp[i][j]`：前`i`个物品，容量`j`时的最优解	选物品：`dp[i-1][j-w[i]] + v[i]`；不选：`dp[i-1][j]`；取两者最优
完全背包	`dp[i][j]`：前`i`个物品，容量`j`时的最优解	选物品：`dp[i][j-w[i]] + v[i]`；不选：`dp[i-1][j]`；取两者最优

核心区别：完全背包选物品时，复用当前行的状态（允许重复选当前物品）；0-1 背包仅复用上一行的状态（仅能选一次）。

一维滚动数组优化版（面试通用）

背包类型	状态定义	核心遍历规则	状态转移方程
0-1 背包	`dp[j]`：容量`j`时的最优解	容量倒序遍历（从`C`到`w[i]`），避免重复选取物品	`dp[j] = max/min(dp[j], dp[j-w[i]] + v[i])`
完全背包	`dp[j]`：容量`j`时的最优解	容量正序遍历（从`w[i]`到`C`），允许重复选取物品	`dp[j] = max/min(dp[j], dp[j-w[i]] + v[i])`