从「求最值」到「换一个聚合算子」

到这里，背包的容量骨架已经很熟：枚举物品、逐容量转移、一维 $f[j]$ 由 $f[j-w]$ 推来。前面几类都在问同一件事，价值最大是多少，所以转移里坐着一个 $\max$ 。可现实里的问题未必都求最优：「恰好花光 $m$ 元有多少种点法？」「这堆砝码能不能称出重量 $j$ ？」

容量骨架原封不动，只换掉中间的聚合算子：max 得最优、+ 得方案数、|| 得可行性，同一套表，三种问题。

关键洞察是：背包的骨架和「求什么」是解耦的。把转移中的 $\max$ 换成加法 $+$ ， $f[j]$ 的含义就从「最大价值」变成「凑出 $j$ 的方案数」；换成逻辑或 $\lor$ ，就变成「 $j$ 能否被凑出」的布尔判定。物品怎么取、循环怎么转，一个字都不用改。这一节就把最常考的一支，方案数背包，讲透，再看它的一个漂亮延伸：撤销。

方案数：把 max 换成加法，f[0] 换成 1

设 $f[j]$ 表示恰好装满容量 $j$ 的方案数。对第 $i$ 件物品（重量 $w_i$ ），凑出 $j$ 的方案分两类：不含它，数目已记在旧的 $f[j]$ 里；含它，先把它占的 $w_i$ 抠掉，剩下的 $j-w_i$ 由前面的物品去凑，方案数正是 $f[j-w_i]$ 。两类不重不漏，加起来就是新的 $f[j]$ ：

f[j] \mathrel{+}= f[j-w_i]\qquad (j:\,m\to w_i)

和 01 背包一样倒序，每件至多计入一次，倒序让 $f[j-w_i]$ 停在「这件还没参与」的旧值上。真正的分水岭在初值：

f[0]=1,\qquad f[j]=0\ (j>0)

为什么 $f[0]=1$ ？因为「凑出容量 0」有且只有一种办法，什么都不装（空方案）。这个 1 是所有计数的种子：它顺着 $\mathrel{+}=$ 一路传播，每落到一个能被凑出的容量，就点亮一种新组合。若把它写成 0，整张表会永远是 0，一种方案也数不出来。

本质 · 算子决定问题，骨架不动

背包框架回答的是「用这些物品凑容量」这件事本身；把结果如何聚合，是另一个正交的维度。 $\max$ （最优）、 $+$ （计数）、 $\lor$ （可行）只是同一骨架上换插头。计数型的两处硬改动就记死： $\max\to +$ 、 $f[0]=1$ 。

还有一个常混的点：「恰好装满」还是「不超过」？看你把种子撒在哪、答案读哪格。要「恰好装满 $m$ 」，就只让 $f[0]=1$ （唯一合法的空起点），答案读 $f[m]$ ；若问「总重不超过 $m$ 的方案数」，则把 $f[0..m]$ 全设成 1（任何容量都允许「空着」），或最后对 $f[0..m]$ 求和。本页例题走的都是「恰好」这一支。

跟着算一遍：两条组合各贡献 1

用三件物品 $w=(2,3,5)$ 、目标容量 $5$ 走一遍。手上先想清答案：恰好凑出 5 的子集只有 $\{2,3\}$ 和 $\{5\}$ 两个，所以 $f[5]$ 该等于 2。看表怎么把这 2 数出来：

0

撒种子。

f[0]=1

，其余

f[1..5]=0

。此刻只有「空方案」这一种被记下。

1

放物品 1（

w=2

），倒序

j:5\to 2

。只有

f[2]\mathrel{+}=f[0]=1

有效，其余来源都是 0。表变成

1,0,1,0,0,0

，凑出 2 有 1 种（就

\{2\}

）。

2

放物品 2（

w=3

），倒序

j:5\to 3

。

f[5]\mathrel{+}=f[2]=1

（这就是

\{2,3\}

！）、

f[3]\mathrel{+}=f[0]=1

。表变成

1,0,1,1,0,1

。

3

放物品 3（

w=5

），倒序

j:5

。

f[5]\mathrel{+}=f[0]=1

（这是

\{5\}

）。

f[5]

从 1 加到 2，两条组合各贡献 1，和手数吻合。

三件全部做完后 f[0..5]=1,0,1,1,0,2：容量 5 由 {2,3} 与 {5} 两条路各累加 1，最终方案数 2。

下面的演示把

f[j]

逐格累加给你看，高亮每一步是从哪个

f[j-w]

加过来的。改物品重量或目标容量，看方案数实时重算。

看方案数一格一格叠出来

恰好装满容量 W = 5 的方案数：f[5] = 2

0

1

2

3

4

5

f

1

0

当前计算依赖来源被选转移已确定

f[0]=1,\ f[j]=0\ (j>0)

初始：f[0]=1（凑出容量 0 有唯一一种方案，空方案），其余 f[j]=0（还没有物品可用，凑不出来）。这一步取代了最优 DP 里的「全 0」地基。

进度

已暂停，第 1 步，共 10 步，1 倍速

深化 · 撤销：正难则反，把某件「退」出去

方案数背包有一个极漂亮的延伸。设想这样的问题（洛谷 P4141「消失之物」）： $n$ 个物品，对每一个物品 $k$ ，都要回答「假如第 $k$ 件消失了，凑出体积 $j$ 的方案数是多少」。最笨的办法是抠掉一件、重算一遍整张表， $n$ 件就是 $n$ 遍， $O(n^2 m)$ ，太慢。

正难则反：与其一件件「不放进去」，不如先把全部物品都放进去算出全集方案数 $f[j]$ ，再针对要消失的那件做一次逆操作，把它对 $f$ 的贡献「退」掉。当初加它是 $f[j]\mathrel{+}=f[j-w_k]$ ，那么退它就是它的逆：

g[j] \mathrel{-}= g[j-w_k]\qquad (j:\,w_k\to m)

先算含全部物品的 g[j]，再对第 k 件逆操作 g[j] −= g[j−w]，得到「缺这件」的方案数。加它倒序、退它正序，方向恰好相反。

方向是这里唯一的陷阱。回想计数为什么倒序：为了让 $f[j-w]$ 保持「本件还没加入」的干净旧值。撤销要的恰恰相反，算 $g[j]$ 时，我需要 $g[j-w_k]$ 已经是「本件退干净」的值，这样减出来的 $g[j]$ 才不含第 $k$ 件。而 $j-w_k < j$ ，所以必须让小下标先被退，也就是 $j$ 从 $w_k$ 正序涨到 $m$ 。把方向记反，退出来的就是一堆错数。

常见陷阱 · 撤销的方向与加时相反

加一件物品用倒序（ $j:m\to w$ ），撤一件物品用正序（ $j:w\to m$ ），这不是可选项，是逆操作的内在要求：撤销时 $g[j]$ 依赖已经退干净的 $g[j-w]$ ，故小下标必须先处理。此外别在原数组上直接减（会污染下一件的撤销），每次从全集 $f$ 拷一份 $g$ 再退；带模数时减法记得 $+\text{MOD}$ 再取模，避免出现负数。

看它把一件「退」出去

先看第一幕把全部物品倒序累加成全集

f[j]

；再挑「让第几件消失」，第二幕会拷一份

g\gets f

，对那件正序逐格做

g[j]\mathrel{-}=g[j-w_k]

，注意方向和加时（倒序）相反。末帧上下两行并排：全集

f[j]

vs 缺那件的

g[j]

。留意默认这组：

w=(2,3,5)

、

W=5

时全集

f[5]=2

，让

w=5

那件消失后

g[5]

退成 1（只剩

\{2,3\}

），方案数从 2 降到 1，退掉的正是用到它的那条。

让第几件「消失」（对它做逆操作退掉）

全集 f[5] = 2 ，让第 3 件（w=5）消失后，缺它的方案数 g[5] = 1，退掉了 1 种「用到第 3 件」的方案。

0

1

2

3

4

5

f 全集

g 缺#3

1

0

·

当前计算依赖来源被选转移已确定

f[0]=1,\ f[j]=0\ (j>0)

第一幕 · 先把全部物品都放进去。初值 f[0]=1（空方案），其余 f[j]=0。下面按标准计数背包倒序累加，建出含全部 3 件的全集方案数 f[j]。

进度

已暂停，第 1 步，共 13 步，1 倍速

例题

P1164小 A 点菜洛谷原生普及-

题意

n

道菜价格已知，手上恰好

m

元，求恰好花完这

m

元的点菜方案数。

对应关系

「价格」= 重量

w

，「手上的钱

m

」= 目标容量。每道菜至多点一次 → 计数型 01 背包。

为什么选它

从「最优 DP」跨到「计数 DP」最平滑的一题：转移里的

\max

原样换成

+

、初值置

f[0]=1

，其余骨架分毫不动。是理解「换算子」的入门标杆。

转移 · 复杂度

f[j]\mathrel{+}=f[j-a_i]

，一维倒序、

f[0]=1

；答案

f[m]

，时间

O(nm)

。方案数可能较大，用 $\texttt{long long}$ 。

参考代码（01 计数）

C++

在洛谷打开 P1164

#include <iostream>
using namespace std;

int a[105];
long long f[10005];          // f[j]：恰好花 j 元的方案数（方案数常爆 int，用 long long）

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    f[0] = 1;                           // ★地基：花 0 元有 1 种方案（什么都不点）
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= a[i]; j--) // 倒序：每道菜至多点一次（01）
            f[j] += f[j - a[i]];        // ★把 max 换成累加，就从「求最优」变「数方案」

    cout << f[m] << endl;
    return 0;
}

P4141消失之物洛谷原生提高+/省选-

题意

n

个物品各有体积

w_i

。对每个

i

，求「第

i

件消失后，用其余物品恰好凑出体积

j

（

1\le j\le m

）」的方案数。

为什么选它

「对每件都要缺它一次的方案数」，直接重算是

O(n^2m)

。此题逼你用撤销（正难则反）：先算全集

f

，再对每件做逆操作退掉贡献，把

n

遍重算压到

O(nm)

。是「计数 DP 可逆」这一思想最经典的载体。

换个视角

背包转移在计数意义下是可逆的：加它

f[j]\mathrel{+}=f[j-w]

的逆就是退它

g[j]\mathrel{-}=g[j-w]

。唯一要翻转的是循环方向，加倒序、退正序。

转移 · 复杂度

全集

f[j]\mathrel{+}=f[j-w_i]

（倒序）；对每件拷

g\gets f

后

g[j]\mathrel{-}=g[j-w_i]

（正序）。时间

O(nm)

，按题意对结果取模。

参考代码（全集 + 撤销）

C++

在洛谷打开 P4141

#include <iostream>
using namespace std;

const int MOD = 10;
int w[2005];
int f[2005], g[2005];        // f：含全部物品的方案数；g：撤销某件后的临时方案数

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i];

    f[0] = 1;                           // 全集方案数：标准计数背包
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= w[i]; j--) // 加它：倒序
            f[j] = (f[j] + f[j - w[i]]) % MOD;

    for (int i = 1; i <= n; i++)        // 逐个「消失」的物品 i
    {
        for (int j = 0; j <= m; j++)
            g[j] = f[j];                // 从全集出发

        for (int j = w[i]; j <= m; j++) // ★退它：正序，方向与加时相反
            g[j] = (g[j] - g[j - w[i]] + MOD) % MOD;   // 逆操作：把第 i 件的贡献减掉

        for (int j = 1; j <= m; j++)    // 缺第 i 件时，体积 j 的方案数
            cout << g[j];
        cout << endl;
    }
    return 0;
}

练习

P2347[NOIP1996 提高组] 砝码称重布尔可行变形：f[j] 表示「重量 j 能否被称出」，把 max 换成逻辑或 f[j] |= f[j-w]，f[0]=true；每种砝码有限个，按多重背包逐件处理，最后数一遍有多少个 j 为真。在洛谷打开

P2563[AHOI2001] 质数和分解完全背包求方案数：先筛出不超过 n 的质数当「无限件物品」，f[j] += f[j-p] 正序（每种质数可重复用），f[0]=1；f[n] 即把 n 写成若干质数之和的无序分解数。在洛谷打开

P1077[NOIP2012 普及组] 摆花有限件求方案数：f[j] 表示恰好摆 j 盆的方案数，第 i 种花取 0..a_i 盆；朴素枚举件数是 O(n·m·a)，可对「枚举本种取几盆」那一维用前缀和优化掉一维。在洛谷打开

背包综合变形

本课摘要

从「求最值」到「换一个聚合算子」

方案数：把 max 换成加法，f[0] 换成 1

本质 · 算子决定问题，骨架不动

跟着算一遍：两条组合各贡献 1

看方案数一格一格叠出来

深化 · 撤销：正难则反，把某件「退」出去

常见陷阱 · 撤销的方向与加时相反

看它把一件「退」出去

例题

练习