疯狂的背包问题(18) - 求最优方案总数

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

在 01 背包 DP 的同时维护方案计数 dp2，dp 值更大时覆盖计数，相等时累加计数，滚动数组倒序成组。

OJ: luogu

题目 ID: U662097

难度:普及+/提高-

标签:动态规划背包

日期: 2026-08-08 23:13

目录

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

题意

N≤100N \le 100 个物品，01 背包，容量 V≤100V \le 100。求达到最大价值的方案总数，对 109+710^9+7 取模。

思路

一句话本质：在 DP 最优值的同时维护一个平行数组 cnt[c]——DP 值被"更大"覆盖时，计数也被覆盖；DP 值"相等"时，计数累加。

先看一个朴素做法理解题意：

python
#!/usr/bin/env python3
import sys

MOD = 10 ** 9 + 7
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
cnt = 0

for mask in range(1 << n):
    total_v = 0
    total_w = 0
    for i in range(n):
        if mask >> i & 1:
            total_v += v[i]
            total_w += w[i]
    if total_v > V:
        continue
    if total_w > best_val:
        best_val = total_w
        cnt = 1
    elif total_w == best_val:
        cnt += 1

print(cnt % MOD)

枚举所有 2N2^N 种选法，统计最优值对应的方案数。N 到 20 就受不了了。

DP 滚动数组算最优值大家都会：dp[c] = max(dp[c], dp[c-v]+w)。方案数怎么跟上来？

维护一个跟 dp 一样长的数组 cnt[c]，表示"达到 dp[c] 的方案数"。对于物品 i（体积 v、价值 w），从 c = V 倒序到 v：

  • 算一遍候选值：val = dp[c-v] + w。
  • 如果 val > dp[c]：发现更大的值，dp[c] = val，计数也要更新为前驱的位置的计数：cnt[c] = cnt[c-v]。
  • 如果 val == dp[c]：发现了另一条达到相同最优值的路，cnt[c] = (cnt[c] + cnt[c-v]) % MOD。
  • 如果 val < dp[c]：什么都不做。

为什么不用二维数组，直接用滚动数组？

因为计数只关心最终的 cnt[V]，不关心过程路径。滚动数组在正确的逆序下，计数逻辑完全正确——cnt[c-v] 恰好是考虑前 i−1 件的方案数。

cnt 的初值怎么设？

cnt[0..V] 全部初始化为 1。因为空集（不选任何物品）对于任何一个容量 c 来说，都是价值为 0 的方案。当后面加入物品后，dp[c] 可能变成更大的值，对应的 cnt[c] 会被覆盖或累加。

代码

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 = 105;
const int MAXV = 105;
const int MOD = 1000000007;

int n, V;
int v[MAXN], w[MAXN];
int dp[MAXV];   // dp[c] 表示容量不超过 c 时的最大价值
int cnt[MAXV];  // cnt[c] 表示达到 dp[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];

    // 初始化：空集是每一种容量下价值为 0 的唯一方案
    for (int c = 0; c <= V; ++c) cnt[c] = 1;

    // 01 背包 DP + 方案计数
    for (int i = 1; i <= n; ++i) {
        for (int c = V; c >= v[i]; --c) {
            int val = dp[c - v[i]] + w[i];
            if (val > dp[c]) {
                dp[c] = val;
                cnt[c] = cnt[c - v[i]];
            } else if (val == dp[c]) {
                cnt[c] = (cnt[c] + cnt[c - v[i]]) % MOD;
            }
        }
    }

    cout << cnt[V] % MOD << '\n';
    return 0;
}

复杂度

滚动数组 DP，每个物品遍历一次所有容量，O(N⋅V)O(N \cdot V)。N,V≤100N, V \le 100，轻松通过。

总结

求最优方案总数 = DP 最优值 + 同步维护计数。核心只有两句话：

  1. 更大就覆盖：cnt[c] = cnt[c-v]
  2. 相等就累加：cnt[c] += cnt[c-v]

初值 cnt[0..V] = 1 是因为空集是所有容量的起点方案。