A背包 DP

完全背包

无限件·一维正推

本课摘要

完全背包课程回答“物品可无限取用时，正序更新如何复用本轮状态”。内容以无限件·一维正推为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。

  • 判断完全背包的适用条件与状态边界
  • 围绕“无限件·一维正推”推导转移与计算顺序
  • 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节

正在整理目录…

同一种物品，取之不尽

完全背包与 01 背包只差一个字：01 里每件要么取要么留，完全里每种物品有无限件，同一种想拿几件就拿几件。 目标不变，在不超过容量的前提下，让装入的总价值最大。

×∞物品 1w=2v=3×∞物品 2w=3v=5背包容量 m=9
每种物品都带 ×∞：容量 m=9 时，物品 1（w=2,v=3）可拿到 4 件价值 12，物品 2（w=3,v=5）可拿 3 件价值 15，同一种可反复取用。

状态定义也不用改：f[j]f[j] 仍表示容量不超过 jj 时的最大价值。变的只有一件事， 「考虑第 ii 种物品」这个动作，现在可以对同一种反复施加，而不是只做一次决断。

与 01 只差一个方向：正推即「允许重复」

转移方程写出来，和 01 背包的一维式子一模一样：

f[j]=max⁡(f[j], f[j−wi]+vi)f[j]=\max\big(f[j],\ f[j-w_i]+v_i\big)

差别只在循环方向：01 背包逆推（jj 从 mm 到 wiw_i，保证每件至多取一次）， 完全背包正推（jj 从 wiw_i 到 mm）。就这一处方向之差，决定了「每种一件」还是「每种无限件」。

本质 · 为什么正推就对了

正推时算 f[j]f[j] 用到的 f[j−wi]f[j-w_i]，可能已经包含了第 ii 种，于是这一种被自然地再取一次。 这正是 01 背包「不能正推」那一节里的同一个机制：在 01 里它是要极力避开的 bug，在完全背包里它恰恰是我们想要的特性。同一段转移，方向决定物种。

为什么还是 O(nm)：从枚举件数到一次转移

「无限件」听起来更复杂，最朴素的想法是枚举第 ii 种取几件：取 0,1,2,…0,1,2,\dots 件各算一遍再取最大，

f[i][j]=max⁡k≥0 (f[i−1][j−k wi]+k vi)f[i][j]=\max_{k\ge 0}\ \big(f[i-1][j-k\,w_i]+k\,v_i\big)

这比 01 多了一层「枚举件数」，复杂度升到 O ⁣(nm⋅m/w)O\!\big(nm\cdot m/w\big)。但盯住 f[i][j−wi]f[i][j-w_i] 看：它本身已经是「前 ii 种、容量 j−wij-w_i」把所有件数都枚举过的最优，已经包含了「再多取一件第 ii 种」的全部可能。于是那一整层枚举可以折叠成一步：

f[i][j]=max⁡(f[i−1][j], f[i][j−wi]+vi)f[i][j]=\max\big(f[i-1][j],\ f[i][j-w_i]+v_i\big)
01 · 取来自上一行i−1ij−wjf[i−1][j−w]f[i−1][j]·f[i][j]完全 · 取来自本行i−1ij−wjf[i−1][j−w]f[i−1][j]f[i][j−w]f[i][j]
唯一的差别在「取」这条转移的来源：01 背包指向上一行 f[i−1][j−w]（这一种只能用一次）；完全背包指向本行 f[i][j−w]（这一种刚刚可能已经取过，于是能再取）。正是「同一行回看」把复杂度压回 O(nm)。

降到一维后，f[i][⋅]f[i][\cdot] 与 f[i−1][⋅]f[i-1][\cdot] 共用同一个数组，「本行的 f[j−wi]f[j-w_i]」正是正推时那个已被本种更新过的值，上一节循环方向的由来，到这里就完全说通了。

跟着算一遍：看它把一件反复拿

拿一件物品 (w,v)=(2,3)(w,v)=(2,3)、容量 6，把正推 j:2→4→6j:2\to 4\to 6 走一遍：

0
初始化。 空背包，任何容量下价值都是 0：f[0..6]=0f[0..6]=0。
1
正推到 j=2j=2。 f[2]=max⁡(f[2],f[0]+3)=3f[2]=\max(f[2],f[0]+3)=3，放进第 1 件。
2
正推到 j=4j=4。 此刻 f[2]=3f[2]=3 已经含这件了，f[4]=f[2]+3=6f[4]=f[2]+3=6，同一种又拿了 1 件，共 2 件。
3
正推到 j=6j=6。 f[6]=f[4]+3=9f[6]=f[4]+3=9，第 3 件。容量 6、每件重 2，最多 3 件，总价值 9。这就是完全背包要的答案。
下面的演示会把 f[j]f[j] 沿正方向逐格累积填满，高亮同一件物品被反复计入的来源。改物品或容量，看表实时重算。

看它累积起来

改物品与容量，观察 f[j]f[j] 如何沿正方向累积，同一件物品在一条链上被反复加进来。这与 01 背包的 「顺推 bug」是同一个机制，只是这里它是特性而非缺陷。

自主设计数值
完全背包每种物品可重复取用 · 容量正序更新
物品种类（每种可重复取用，最多 8 种）
1
重量 w
价值 v
2
重量 w
价值 v
背包容量（直接输入 1–60）
m
0
1
2
3
4
5
6
7
8
9
f
0
0
0
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…W 的最大价值都是 0（空背包）。
已暂停，第 1 步，共 17 步，1 倍速

01 还是完全？并排看差别

同一组物品、同一容量，左边按 01（每种至多 1 件）、右边按完全（每种无限件）各算一遍，改改 w,vw,v 和容量， 看完全背包如何靠反复取用同一种，拿到不低于 01 的价值。

物品（可改重量 / 价值）
1
重量 w
2
价值 v
3
2
重量 w
3
价值 v
5
背包容量
m
9
01 最优 f[9] = 8（每种至多 1 件） · 完全最优 f[9] = 15（多拿 7，靠反复取用同一种）
01 背包 · 逆推（每种一件）
0
1
2
3
4
5
6
7
8
9
f
0
0
0
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…W 的最大价值都是 0（空背包）。
已暂停，第 1 步，共 17 步，1 倍速
完全背包 · 正推（每种无限件）
0
1
2
3
4
5
6
7
8
9
f
0
0
0
0
0
0
0
0
0
0
当前计算 依赖来源 被选转移 已确定
f[j]=0f[j]=0
初始：容量 0…W 的最大价值都是 0（空背包）。
已暂停，第 1 步，共 17 步，1 倍速

例题

P1616疯狂的采药洛谷原生普及/提高-
题意
与 P1048 采药同型，但每株草药可采无限次。求 TT 时间内最大价值。
为什么选它
和 01 背包的 P1048 构成「逆推 ↔ 正推」黄金对照，代码只差内层循环方向，一眼看清两类背包的分界。
数据范围 · 别照搬 P1048 的数组
本题 T≤107T\le 10^7，所以 ff 要按时间上限开到 107+510^7+5；最优价值还可能超过 32 位整数，数组必须用 long long。若仍写成 P1048 常见的 int f[10005]，大数据会越界或溢出。
参考代码（一维正推）
C++
在洛谷打开 P1616 
#include <iostream>
#include <algorithm>
using namespace std;

int t[10005], v[10005];
long long f[10000005];        // 1 <= T <= 10^7，答案也可能超过 int

int main()
{
    int T, M;
    cin >> T >> M;
    for (int i = 1; i <= M; i++)
        cin >> t[i] >> v[i];

    for (int i = 1; i <= M; i++)
        for (int j = t[i]; j <= T; j++)     // ★正推：允许同一物品被重复取
            f[j] = max(f[j], f[j - t[i]] + v[i]);

    cout << f[T] << endl;
    return 0;
}
P5662[CSP-J2019] 纪念品CSP-J 2019普及+/提高
题意
TT 天、nn 种纪念品，每天可无限量买卖。用初始金币 mm，问 TT 天后最多有多少金币。
为什么选它
较新的 CSP-J 真题：把「当天买、次日卖」的收益当价值，每天做一次完全背包，收益并入本金滚动。是「完全背包 + 贪心持币」的贴近真题的代表。
参考代码
C++
在洛谷打开 P5662 
#include <iostream>
#include <algorithm>
using namespace std;

int p[105][105];             // p[d][j]：第 d 天第 j 种纪念品价格
int f[100005];

int main()
{
    int T, n, m;
    cin >> T >> n >> m;
    for (int d = 1; d <= T; d++)
        for (int j = 1; j <= n; j++)
            cin >> p[d][j];

    for (int d = 1; d < T; d++)             // 枚举每一天，用当天买、次日卖
    {
        for (int j = 0; j <= m; j++) f[j] = 0;      // 每天现金独立，重置
        for (int j = 1; j <= n; j++)                // 每种纪念品可买多份 → 完全背包
            for (int c = p[d][j]; c <= m; c++)      // ★正推
                f[c] = max(f[c], f[c - p[d][j]] + p[d + 1][j] - p[d][j]);
        m += f[m];                           // 当天最优收益并入本金
    }

    cout << m << endl;
    return 0;
}
P5020[NOIP2018 提高组] 货币系统NOIP2018 提高提高+/省选-
题意
给定 nn 种面值的货币系统，求一个面值种数最少的等价系统（能表示的金额集合完全相同）。
换个视角看完全背包
把完全背包当「可表示性判定」工具：面值从小到大处理，若当前面值已能被更小的保留面值凑出（f[ai]f[a_i] 为真），它就是多余的；否则必须保留，并作为一件完全背包物品去标记新的可达金额。答案即保留的面值数。
转移 · 复杂度
可达性递推 f[j] ∣= f[j−ai]f[j]\ |=\ f[j-a_i]（正推）；时间 O(n⋅amax⁡)O(n\cdot a_{\max})。是「完全背包 ≠ 只会求最值」的最佳一课。
参考代码
C++
在洛谷打开 P5020 
#include <iostream>
#include <algorithm>
using namespace std;

int a[105];
bool f[25005];               // f[j]：用已保留的面值能否凑出金额 j

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        sort(a + 1, a + n + 1);              // 从小到大处理

        int m = a[n];                        // 最大面值即可达范围上界
        for (int j = 0; j <= m; j++) f[j] = false;
        f[0] = true;

        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (!f[a[i]])                    // 这个面值凑不出来 → 必须保留
            {
                cnt++;
                for (int j = a[i]; j <= m; j++)     // 完全背包正推标记可达
                    f[j] = f[j] || f[j - a[i]];
            }

        cout << cnt << endl;
    }
    return 0;
}

练习

P2918[USACO08NOV] Buying Hay S完全背包求最小花费；注意可以「超采」，容量要开到 m + 最大单件重量，再在 ≥ m 的区间取最小。在洛谷打开
P2725[USACO3.1] 邮票 Stamps可达性完全背包：f[j] 表示凑出面值 j 最少用几张邮票，求从 1 起最长连续可凑区间。在洛谷打开
P1832A+B Problem（再升级）完全背包求方案数：把 n 分解为若干质数之和，先筛质数当物品，f[j] 累加（注意开 long long）。在洛谷打开
回到 A 部分页的「装包大师」时，不妨设想若同一件宝物可以无限件地装，完全背包正是把「每件只拿一次」的枷锁彻底松开的那一步。

已进入 完全背包 · 背包 DP · DP大师