疯狂的背包问题(19) - 求恰好装满的最优方案数

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

dp 初始值区分可达与不可达：dp[0]=0 可达，其他 dp[c]=-INF 不可达。只有从可达前驱转移才参与计数。

OJ: luogu

题目 ID: U662107

难度:普及+/提高-

标签:动态规划背包

日期: 2026-08-08 23:13

目录

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

题意

N≤100N \le 100 个物品，01 背包，容量 V≤100V \le 100。要求恰好装满容量 V，输出此时最大价值的方案总数，对 109+710^9+7 取模。若无法恰好装满则输出 0。

思路

一句话本质：恰好装满与不要求装满的唯一区别在 DP 初值——只有 dp[0]=0 可达，其余 dp[c]=-INF 不可达，计数也只在可达状态之间转移。

先看枚举法确认题意：

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 = -1
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)

枚举所有方案，只统计体积恰好等于 V 的，再从中挑出价值最大的计数。

普通 01 背包的 dp[c] 含义是"容量不超过 c 的最大价值"，初值全 0。为什么恰好装满不能这样初始化？

因为全 0 初值意味着"容量 c 的价值至少是 0（不选任何物品）“，它隐含了"可以不满"的自由。要强制恰好装满，必须让非零容量的"空集"变成非法状态——用 -INF 表示"这个容量在当前没有任何合法方案可达”。

dp[0]=0, dp[1..V]=-INF 后转移公式变了吗？

公式写法不变：dp[c] = max(dp[c], dp[c-v] + w)。但前提是 dp[c-v] != -INF——前驱必须可达。如果 dp[c-v] 是 -INF，dp[c-v] + w 是一个同样没有意义的数（负数极大值的加法），必须跳过。

计数怎么配合？

同样只有可达状态才有计数。初始化：cnt[0]=1，cnt[1..V]=0。转移逻辑与方案总数题一致，但必须加一层可达性判断：

text
如果 dp[c-v] == -INF：跳过，前驱不可达。
否则 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

最后答案怎么取？

若 dp[V] == -INF，说明没有任何方案能恰好装满 V，输出 0。否则输出 cnt[V]。

代码

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;
const int INF = 0x3f3f3f3f;

int n, V;
int v[MAXN], w[MAXN];
int dp[MAXV];   // dp[c] 表示恰好装满容量 c 时的最大价值，-INF 表示不可达
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];

    // 恰好装满初始化：只有 dp[0] 可达
    for (int c = 1; c <= V; ++c) dp[c] = -INF;
    cnt[0] = 1;

    // 01 背包 DP + 方案计数（恰好装满）
    for (int i = 1; i <= n; ++i) {
        for (int c = V; c >= v[i]; --c) {
            if (dp[c - v[i]] == -INF) continue; // 前驱不可达则跳过
            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;
            }
        }
    }

    if (dp[V] == -INF) cout << 0 << '\n';
    else cout << cnt[V] % MOD << '\n';
    return 0;
}

复杂度

O(N⋅V)O(N \cdot V)，与普通 01 背包一致。

总结

恰好装满背包的所有变种，本质都是修改 DP 初值来约束合法性：

需求 dp 初始化
不超过容量 dp[0..V] = 0
恰好装满 dp[0]=0, dp[1..V]=-INF

初值不同，转移逻辑不变——只需要加一层"前驱可达性"判断。cnt 数组也随之调整初值：不超过容量时 cnt[0..V]=1，恰好装满时 cnt[0]=1, cnt[1..V]=0。