题意

N 种物品，每种可以选任意多件。第 i 种体积 v_i，价值 w_i。背包容量 V。挑选物品使总体积不超过 V 且总价值最大，输出最大价值。

思路

一句话本质：每件物品可选任意次，容量有限制，求最大总价值。

brute.py 的写法为什么不可行？

brute.py 用 dfs 枚举每种物品选 0 到 max_k 件，递归到下一件。每种物品的选择数量不确定，搜索树巨大。N=1000 时指数级分支无法承受。

和 01 背包（每件只能选一次）的本质区别在哪里？

01 背包中，每件物品要么选要么不选，是一次性决策。完全背包中，同一件物品可以反复选——这意味着处理物品 i 时，从 dp[c - v_i] 转移过来后，可能 dp[c - v_i] 本身已经包含了物品 i 的贡献（即已经选过物品 i 了），再转移一次就等于又选了一次物品 i。

为什么把容量枚举方向从倒序改为正序就能实现"无限次使用"？

在 01 背包中，容量倒序保证了 dp[c - v] 是"没选过当前物品"时的值，避免同一物品被重复使用。

而在完全背包中，我们希望允许重复使用。容量正序时，先处理小的 c，dp[c] 可能已经包含物品 i 的贡献；后面更大的 c’ 再从 dp[c’ - v] 转移时，dp[c’ - v] 里可能已经有了物品 i——这就自然实现了"可以再选一次物品 i"。

状态定义和转移是什么？

定义 dp[c] 表示占用容量 c 时能获得的最大价值。

初始 dp[0] = 0。

对于每种物品 (v, w)，容量 c 从 v 到 V 正序：

1dp[c] = max(dp[c], dp[c - v] + w)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:11
 * update_at: 2026-08-08 23:11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1);
    for (int i = 0; i < N; ++i) {
        int v, w;
        cin >> v >> w;
        for (int c = v; c <= V; ++c)
            dp[c] = max(dp[c], dp[c - v] + w);
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

• 时间：O(N × V)，每种物品遍历 V 个容量
• 空间：O(V)，dp 数组大小 V+1

总结

完全背包与 01 背包的唯一代码差异是容量枚举方向：倒序保证每件物品只用一次，正序支持多次使用。本质是 dp[c - v] 是否已经包含了当前物品的贡献——倒序时没包含，正序时可能已包含。