完全背包

一句话算法

完全背包的核心是“每种物品可以选无限次”：处理某个物品时，容量正序枚举，让它可以在本轮被继续使用。

问题模型

给定 $n$ 种物品和容量为 $C$ 的背包。第 $i$ 种物品有：

• 重量 $w_i$；
• 价值 $v_i$；
• 可以选任意多个。

要求总重量不超过 $C$，总价值最大。

完全背包和 01 背包只有一个根本区别：

核心直觉

处理第 $i$ 种物品时，最优方案仍然分成两类：

1. 一个也不选第 $i$ 种物品；
2. 至少选一个第 $i$ 种物品。

如果至少选一个第 $i$ 种物品，可以先拿走一个，剩下的问题仍然是：

前 $i$ 种物品，在容量 $c-w_i$ 下的完全背包。

注意这里是“前 $i$ 种”，不是“前 $i-1$ 种”。因为第 $i$ 种物品还可以继续选。

状态设计

定义：

表示只考虑前 $i$ 种物品，容量为 $c$ 时能得到的最大价值。

边界：

没有物品可选时，价值为 $0$。

状态转移

不选第 $i$ 种物品：

至少选一个第 $i$ 种物品：

因此：

和 01 背包的关键差异是第二项：

01 背包：   dp[i-1][c-w_i] + v_i
完全背包： dp[i][c-w_i] + v_i

完全背包使用 dp[i] 自己这一行，表示第 $i$ 种物品可以继续被选择。

算法步骤

1. 读入 $n,C$ 和每种物品的 $w_i,v_i$。
2. 初始化 dp[0][c] = 0。
3. 枚举物品种类 i = 1..n。
4. 枚举容量 c = 0..C。
5. 先继承“不选第 i 种物品”的答案。
6. 如果 c >= w[i]，尝试从 dp[i][c-w[i]] 转移，表示再选一个第 i 种物品。
7. 输出 dp[n][C]。

算法证明

核心不变量：计算完第 $i$ 行后，dp[i][c] 表示只使用前 $i$ 种物品、容量不超过 $c$ 的最大价值。

1. 分类完整

   任意最优方案对第 $i$ 种物品只有两种情况：选 $0$ 个，或选至少 $1$ 个。

2. 选 $0$ 个

   方案只使用前 $i-1$ 种物品，因此最优值是：

   $$dp[i-1][c]$$

3. 选至少 $1$ 个

   先拿出一个第 $i$ 种物品，容量减少 $w_i$，价值增加 $v_i$。剩下的方案仍然可以继续使用第 $i$ 种物品，所以最优值是：

   $$dp[i][c-w_i]+v_i$$

4. 取最大值

   两类方案覆盖所有可能，取最大值就是最优解。

因此转移正确，算法正确。

复杂度分析

• 二维写法时间复杂度：$O(nC)$。
• 二维写法空间复杂度：$O(nC)$。
• 一维写法时间复杂度：$O(nC)$。
• 一维写法空间复杂度：$O(C)$。

代码实现

二维写法

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n, capacity;
    cin >> n >> capacity;

    vector<int> weight(n + 1), value(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> weight[i] >> value[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int c = 0; c <= capacity; c++) {
            dp[i][c] = dp[i - 1][c];
            if (c >= weight[i]) {
                dp[i][c] = max(dp[i][c],
                               dp[i][c - weight[i]] + value[i]);
            }
        }
    }

    cout << dp[n][capacity] << "\n";
    return 0;
}
    

一维写法

完全背包一维写法中，容量必须正序枚举：

        
1

        for (int c = weight; c <= capacity; c++)
    

正序枚举会让 dp[c-weight] 可能已经在本轮被当前物品更新过，因此当前物品可以被重复选择。

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n, capacity;
    cin >> n >> capacity;

    vector<int> dp(capacity + 1, 0);

    for (int i = 1; i <= n; i++) {
        int weight, value;
        cin >> weight >> value;

        for (int c = weight; c <= capacity; c++) {
            dp[c] = max(dp[c], dp[c - weight] + value);
        }
    }

    cout << dp[capacity] << "\n";
    return 0;
}
    

测试用例

输入：

5 7
6 5
5 4
2 3
4 6
2 6

输出：

18

解释：第 5 种物品重量为 2、价值为 6，可以重复选。容量为 7 时选 3 个，总重量为 6，总价值为 18。

应用分类详解

完全背包的本质是：每种选择可以重复使用。只要题目中的对象不是“一次性资源”，而是可以反复购买、反复使用、反复取用，就应该考虑完全背包。

一、无限物品最大价值

典型模式： 每种物品数量无限，容量有限，求最大价值。

识别信号： 出现“每种可以选任意次”“可以重复购买”“无限供应”。

核心建模： 容量是限制，物品种类是转移来源，容量正序枚举。

二、凑数和方案数

典型模式： 给一些面值，问能否凑出金额，或有多少种凑法。

识别信号： 出现“硬币无限”“凑出金额”“方案数”。

核心建模： dp[c] 可以表示最大价值、最小数量、方案数，转移方向仍是正序。

三、整数拆分和生成函数类问题

典型模式： 一个数可以由若干种基本数值重复组成。

识别信号： 出现“拆成若干个数”“每个数可以用多次”“组成目标值”。

核心建模： 每个可用数值是一种物品，目标和是容量。

经典例题

1. luogu-P1616

完全背包入门题。时间是容量，每种草药可以采任意次。

2. LeetCode 322

把硬币面值当作物品重量，每枚硬币价值视作数量成本，求最少硬币数。

3. LeetCode 518

求组合方案数。外层枚举硬币，内层容量正序枚举，避免排列重复计数。

参考

• 旧版文章：Rbook_ejs_old/book/dynamic_programming/knapsack/full_knapsack/index.md
• 前置：01 背包