背包问题的问法变化

1 问题引入

前面几讲都在求「最大价值」。但同一张图、同一组物品，换一个问法就是新题目。这一讲收集几种常见的变形。

它们的共同点是：状态转移方程基本不变，改的只是「合并」这一步怎么算。

问法	改动
求最小价值 / 最少件数	`max` 换成 `min`
求方案总数	`max` 换成累加 `+`
求最优方案总数	记录方案数，与最优值同步更新
求第 $K$ 优解	每个状态存一个长度为 $K$ 的有序队列
输出具体方案	额外记录「这个值是从哪来的」

2 求方案总数

以完全背包为例，问「装满容量 $C$ 有多少种方案」。转移从取最大值改成累加：

f(j)=\sum f(j-w_i)

初始条件 $f(0)=1$ ——容量 $0$ 有一种方案，就是「什么都不装」。

// 求装满容量 C 的方案总数（完全背包模型：每种物品可用无限次）
// 转移从 max 改成累加，容量正序；f[0]=1 表示「什么都不装」这一种方案
// 方案数可能很大，按常见做法对 1e9+7 取模
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, C;
int w[maxn];
long long f[maxn];

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

    f[0] = 1;                               // 边界：容量 0 有一种方案（空）
    for (int i = 1; i <= n; ++i) {
        for (int j = w[i]; j <= C; ++j) {   // 正序：允许重复用同一种
            f[j] = (f[j] + f[j - w[i]]) % MOD;
        }
    }
    cout << f[C] << endl;
    return 0;
}

样例输入：

输出：

说明为什么是累加而不是取最大

状态转移方程枚举了所有可能的构成方式。取最大只保留了其中最好的一个；累加则把每种方式都记下来。所以「求方案数」和「求最值」共用同一套状态设计，只差一个运算。

3 求最优方案的总数

这里问的是：达到最大价值的方案有几个。

需要两个数组： $f(j)$ 存最大价值， $g(j)$ 存达到该价值的方案数。更新时两者同步：

若 $f(j)<f(j-w)+v$ ：最大价值被刷新， $g(j)$ 也跟着换成 $g(j-w)$ ；
若 $f(j)=f(j-w)+v$ ：多了一种达到同样最优价值的方式， $g(j)$ 累加。

// 求「最优方案的总数」：01 背包，同时维护最大价值 f[] 与达到该价值的方案数 g[]
// 转移时若价值更大则 g 跟着换，若价值相等则 g 累加
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;

int n, C;
long long f[maxn];      // f[j]：容量 j 的最大价值
long long g[maxn];      // g[j]：达到 f[j] 的方案数

int main() {
    cin >> n >> C;

    for (int j = 0; j <= C; ++j) { f[j] = 0; g[j] = 1; }   // 什么都不选也是一种方案

    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = C; j >= w; --j) {                     // 01 背包，容量倒序
            if (f[j] < f[j - w] + v) {
                f[j] = f[j - w] + v;
                g[j] = g[j - w];
            }
            else if (f[j] == f[j - w] + v) {
                g[j] = (g[j] + g[j - w]) % MOD;
            }
        }
    }
    cout << f[C] << " " << g[C] << endl;
    return 0;
}

样例输入：

输出（最大价值与方案数）：

11 1

4 求第 K 优解

把「取最大值」推广成「取前 $K$ 大」。

设 $f(j,k)$ 表示容量 $j$ 的第 $k$ 优解（ $k$ 从 1 开始，1 最好）。转移时：

「不选第 $i$ 件」给出一个有序队列： $f(j,1),f(j,2),\dots$
「选第 $i$ 件」给出另一个有序队列： $f(j-w,1)+v,\,f(j-w,2)+v,\dots$

两者归并，取前 $K$ 个，就是新的 $f(j,\cdot)$ 。

// 01 背包的第 K 优解：每个状态维护一个大小为 K 的有序队列（从大到小）
// 转移 = 把「不选第 i 件」和「选第 i 件」两个有序队列归并，取前 K 个
// 复杂度 O(n C K)
//
// 约定：价值相同的不同方案算同一个解，所以归并时要去重。
// 若某容量下的不同解不足 K 个，输出其中最差的那个（即最后一个有效解）。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 5;
const int NEG = -1e9;

int n, C, K;
int f[maxn][maxn];      // f[j][k]：容量 j 的第 k 优解（k 从 1 开始，1 最好）

int main() {
    cin >> n >> C >> K;

    // 初始：容量 j 只有「什么都不装」一种方案，价值 0
    for (int j = 0; j <= C; ++j) {
        f[j][1] = 0;
        for (int k = 2; k <= K; ++k) f[j][k] = NEG;
    }

    for (int i = 1; i <= n; ++i) {
        int w, v;
        cin >> w >> v;
        for (int j = C; j >= w; --j) {
            // A = 不选第 i 件（f[j] 本身），B = 选第 i 件（f[j-w] 全体 + v）
            int a = 1, b = 1;
            int tmp[maxn], cnt = 0, last = NEG;
            bool hasLast = false;
            while (cnt < K && (a <= K || b <= K)) {
                int va = (a <= K) ? f[j][a] : NEG;
                int vb = (b <= K && f[j - w][b] != NEG) ? f[j - w][b] + v : NEG;
                // 注意：NEG 加上 v 会变成「看起来合法」的数，必须先判空
                if (va == NEG && vb == NEG) break;
                int pick;
                if (va >= vb) { pick = va; ++a; }
                else { pick = vb; ++b; }
                if (hasLast && pick == last) continue;   // 去重：相同价值只留一个
                tmp[++cnt] = pick;
                last = pick; hasLast = true;
            }
            for (int k = 1; k <= cnt; ++k) f[j][k] = tmp[k];
            for (int k = cnt + 1; k <= K; ++k) f[j][k] = NEG;
        }
    }

    // 有效解个数：从头数到第一个 NEG
    int count = 0;
    for (int k = 1; k <= K; ++k) {
        if (f[C][k] == NEG) break;
        count = k;
    }
    int idx = min(K, count);                    // 不足 K 个就取最后一个有效解
    cout << f[C][1] << " " << f[C][idx] << endl;
    return 0;
}

样例输入（第三个数是 $K$ ）：

输出（最优解与第 $K$ 优解）：

11 9

注意两个容易踩的坑

负无穷会「变合法」：无解状态用 $-\infty$ 表示，但 $-\infty+v$ 不再等于 $-\infty$ 。归并时必须先判断该位置是否有解，否则会凭空造出一个合法值。
要不要去重：题目若规定「价值相同但方案不同算同一个解」，归并时就要跳过与前一个相同的值；若算不同解，则不能去重。kth_best.cpp 按「去重」处理。

复杂度从 $O(nC)$ 变成 $O(nCK)$ ——多乘一个 $K$ 。

5 输出具体方案

求最值时丢掉了「这个值是怎么来的」。要输出方案，就得把它记下来。

最直接的做法是再开一个数组 $g(i,j)$ ，记录 $f(i,j)$ 是取了两项中的哪一项。输出时从 $f(n,C)$ 倒着走：

// g[i][j] = 0 表示没选第 i 件，1 表示选了
int i = n, j = C;
while (i > 0) {
    if (g[i][j] == 1) { print(i); j -= w[i]; }
    --i;
}

也可以不存 $g$ ，在回溯时现算：比较 $f(i,j)$ 与 $f(i-1,j)$ 是否相等，相等说明没选第 $i$ 件；否则就是选了。这样省掉一个数组。

说明字典序最小的方案

若要求输出「字典序最小」的最优方案，做法是把物品编号倒过来（ $x\leftarrow n+1-x$ ）再跑标准 DP，输出时换回原编号。这样在「同样最优」时，程序会优先选择编号小的物品。

6 小结

这一讲没有新算法，只有一组「换个运算」的观察：

max → min：最小化类问题；
max → +：方案计数；
max → 有序队列归并：第 $K$ 优解；
额外记录来源：输出方案。

真正要提防的是细节： $-\infty$ 的传播、要不要去重、初始化怎么写。这些地方错了，程序照样跑，只是答案是错的。

7 相关题解

暂无相关题解