疯狂的背包问题(16) - 输出字典序最小的最优方案

题意

$N$ 个物品，01 背包，容量 $V$ 。求字典序最小的最优方案——即所选物品编号序列在字典序意义下最小。

思路

一句话本质：先用 DP 求出每个容量下的最优值，再从编号 1 开始贪心回溯：如果选当前物品后剩余容量仍能达到相同最优值，就必选它。

先看一个能直接验证对错的朴素枚举：

python

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
28
29
30
31
32
33#!/usr/bin/env python3
import sys

data = list(map(int, sys.stdin.buffer.read().split()))
n, V = data[0], data[1]
v = data[2:2 + 2 * n:2]
w = data[3:3 + 2 * n:2]

best_val = 0
best_scheme = None

for mask in range(1 << n):
    total_v = 0
    total_w = 0
    scheme = []
    for i in range(n):
        if mask >> i & 1:
            total_v += v[i]
            total_w += w[i]
            scheme.append(i + 1)
    if total_v > V:
        continue
    if total_w > best_val:
        best_val = total_w
        best_scheme = scheme
    elif total_w == best_val and best_scheme is not None:
        if scheme < best_scheme:
            best_scheme = scheme

if best_scheme:
    print(*best_scheme)
else:
    print()

枚举所有 $2^N$ 种方案，记录最优值以及字典序最小的方案。用它验证小数据的 DP 结果。

01 背包求最优值没难度，难的是怎么无损还原方案？

DP 只保留了最优值，丢了路径。要还原方案，必须记住每步决策。二维 DP 表 f[i][c] 天然记录了"考虑前 i 件物品、容量 c 时的最大价值"，可以从末状态倒推每一步的决策。

从末状态倒推得到的是字典序最小的方案吗？

不是。从后往前回溯时，编号大的物品会被先考虑，只能得到某个最优方案，不能保证字典序最小。要想优先迁就编号小的物品，必须让决策顺序反过来：先决定物品 1 选不选，再决定物品 2，以此类推。

怎么让决策顺序从编号 1 开始？

一个巧妙的做法是 从后向前 DP。定义 f[i][c] 为只考虑物品 i..N、容量为 c 时的最大价值。DP 从 i=N 递减到 1。这样，f[1][V] 就是全局最优值。回溯时从物品 1 开始依次判断：

如果 c >= v[i] 且 f[i][c] == f[i+1][c - v[i]] + w[i]（选物品 i 能达到最优值），就选它，容量减掉 v[i]，继续往后看。
否则不选，直接看下一件。

为什么这样一定得到字典序最小的方案？

因为从编号 1 开始，只要有"选"这条分支能走到最优值，就立即选它。这等价于在所有最优方案中，优先把编号小的物品固定为"选"，再固定下一个，贪心保证了字典序最小。编号小的物品能选就选——这正是字典序的本质。

代码

cpp

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * 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:13
 * update_at: 2026-08-08 23:59
 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 105;
int n, V;
int v[MAXN], w[MAXN];
int f[MAXN][MAXN]; // f[i][c] 表示考虑物品 i..N，容量为 c 时的最大价值

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    cin >> n >> V;
    for (int i = 1; i <= n; ++i) cin >> v[i] >> w[i];

    // 从后向前 DP：f[i][c] = 使用物品 i..N 的最优值
    for (int i = n; i >= 1; --i) {
        for (int c = 0; c <= V; ++c) {
            f[i][c] = f[i + 1][c];
            if (c >= v[i]) f[i][c] = max(f[i][c], f[i + 1][c - v[i]] + w[i]);
        }
    }

    // 从 1 向 N 回溯，优先选取编号小的物品，得到字典序最小的方案
    vector<int> ans;
    int cur = V;
    for (int i = 1; i <= n; ++i) {
        if (cur >= v[i] && f[i][cur] == f[i + 1][cur - v[i]] + w[i]) {
            ans.push_back(i);
            cur -= v[i];
        }
    }

    for (size_t i = 0; i < ans.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

复杂度

DP 耗时 $O(N \cdot V)$ ，回溯耗时 $O(N)$ 。 $N, V \le 100$ ，轻松通过。

总结

字典序最小方案的核心技巧：DP 方向和回溯方向反过来。如果回溯时需要从编号 1 开始决策，DP 就从编号 N 开始计算。这样回溯时只需贪心判断"选不选"，不需要比较方案。

疯狂的背包问题(16) - 输出字典序最小的最优方案

目录

题意

思路

代码

复杂度

总结