疯狂的背包问题(17) - 求所有最优方案

GitHub跳转原题关系图Canvas 关系图返回列表

先 DP 得到二维最优值表，再用 DFS 回溯所有能走到最优值的分支，收集全部最优方案并按字典序输出。

OJ: luogu

题目 ID: U662039

难度:普及+/提高-

标签:动态规划背包搜索

日期: 2026-08-08 23:13

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

N≤30N \le 30 个物品，01 背包，容量 V≤100V \le 100。输出所有能达到最大价值的方案，按字典序从小到大排列。

思路

一句话本质：二维 DP 表记录了所有的最优转移路径，DFS 回溯这张表就能枚举出所有最优方案。

先看一个枚举所有可能方案的朴素解：

python
#!/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_schemes = []

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_schemes = [scheme]
    elif total_w == best_val:
        best_schemes.append(scheme)

best_schemes.sort()
for scheme in best_schemes:
    if scheme:
        print(*scheme)
    else:
        print()

枚举 2N2^N 种方案，挑出价值最大的所有方案，排序输出。N 较小时正确，但 N 到 30 就超时了。

DP 只能求最优值，怎么知道有哪些方案能达到最优值？

二维 DP 表 f[i][c] 记录了"考虑前 i 件物品、容量 c 时的最大价值"。这张表不仅给了最终答案，还包含了每一层每个容量下的最优值。回溯这张表就能找到所有走到最优值的路径。

怎么回溯？

从物品 N 到物品 1 倒序 DFS。对每个物品 i 和当前容量 c：

  • 不选物品 i 的分支：如果 f[i-1][c] == f[i][c]，说明不选也能达到相同的值，可以沿这条路走下去。
  • 选物品 i 的分支：如果 c >= v[i] 且 f[i-1][c - v[i]] + w[i] == f[i][c]，说明选物品 i 是其中的一条最优路径，记录并沿这条路继续。

两个分支独立，都可以继续 DFS，到达 i==0 时就得到一条完整的方案（DFS 过程中收集的编号需要反转，因为是从后往前记录的）。

为什么不是从容量 V 出发？

最优方案不一定恰好用满容量 V。DP 中 f[N][c] 对于不同的 c 有不同的值，最大价值可能出现在多个容量上（只要不超过 V）。因此需要先找出最优值 best_val，然后对所有使 f[N][c] == best_val 的容量 c 分别回溯。

拿到的方案为什么还要排序？

回溯过程的顺序由 DFS 的递归顺序决定，不一定与字典序一致。收集所有方案后统一排序即可。

代码

cpp
/**
 * 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 = 35;
const int MAXV = 105;
int n, V;
int v[MAXN], w[MAXN];
int f[MAXN][MAXV]; // f[i][c] 表示考虑前 i 件物品，容量为 c 时的最大价值

vector<int> path;          // 当前 DFS 枚举的路径（逆序）
vector<vector<int>> all;   // 所有最优方案

// 从物品 i 向 1 回溯，找出所有能达到 f[i][c] 的方案
void dfs(int i, int c) {
    if (i == 0) {
        // 到边界，记录一条完整方案（path 中编号从大到小，需要反转）
        vector<int> sol = path;
        reverse(sol.begin(), sol.end());
        all.push_back(sol);
        return;
    }

    // 分支1：不选物品 i，要求 f[i-1][c] 也能达到相同最优值
    if (f[i - 1][c] == f[i][c]) {
        dfs(i - 1, c);
    }

    // 分支2：选物品 i，要求容量足够且来自该转移
    if (c >= v[i] && f[i - 1][c - v[i]] + w[i] == f[i][c]) {
        path.push_back(i);
        dfs(i - 1, c - v[i]);
        path.pop_back();
    }
}

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];

    // 正序 01 背包 DP
    for (int i = 1; i <= n; ++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]);
        }
    }

    // 找出最大价值及其对应的容量
    int best_val = 0;
    for (int c = 0; c <= V; ++c) best_val = max(best_val, f[n][c]);

    // 对所有能达到 best_val 的容量 c，回溯收集方案
    for (int c = 0; c <= V; ++c) {
        if (f[n][c] == best_val) {
            dfs(n, c);
        }
    }

    // 按字典序排序后输出
    sort(all.begin(), all.end());
    for (size_t i = 0; i < all.size(); ++i) {
        const vector<int> &sol = all[i];
        for (size_t j = 0; j < sol.size(); ++j) {
            if (j > 0) cout << ' ';
            cout << sol[j];
        }
        cout << '\n';
    }
    return 0;
}

复杂度

DP O(N⋅V)O(N \cdot V)，DFS 回溯在最坏情况下访问所有最优方案。N≤30N \le 30，最优方案总数在可接受范围内。

总结

求所有最优方案的本质是 在 DP 表上做 DFS 回溯。二维 DP 表保留了足够的信息来还原路径——只要检查 f[i-1][c] 和 f[i-1][c-v[i]] + w[i] 是否等于 f[i][c] 即可。这和"求字典序最小方案"的区别在于：前者用贪心选一条路，后者用搜索遍历所有路。