疯狂的背包问题(6) - 完全背包问题（计数组合问题）

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

使用完全背包DP计数恰好装满背包的组合方案数，每种物品无限件，dp[c]+=dp[c-v]，容量正序枚举，对1e9+7取模。

OJ: luogu

题目 ID: U663710

难度:普及-

标签:动态规划完全背包背包

日期: 2026-08-08 23:11

目录

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

题意

N 种物品，每种无限件，每件体积 v_i。问有多少种不同的物品组合方式使总体积恰好等于 V（不考虑放入顺序，只计每种物品选了多少件）。答案对 10^9+7 取模。

思路

一句话本质：每种物品可无限用，数组合方案（只关心每种物品选了几件，不关心顺序）。

brute.py 为什么不可行？

brute.py 对每种物品 dfs 枚举选取 0~max_k 件。当 N 和 V 达到 1000 时，搜索空间爆炸。这不是"常数优化能解决"的问题，而是搜不过来的。

和 01 背包计数问题（U663298）有什么不同？

01 背包计数：每件只能用一次，倒序枚举，是"物品集合的组合计数"。

完全背包计数：每件可用无限次，正序枚举，是"每种物品选取数量的组合计数"。

为什么正序就能实现无限件？

正序枚举容量时，dp[c - v] 可能已经被当前物品更新过了。从 dp[c - v] 转移到 dp[c] 意味着"在已有的选取方案中再多选一件当前物品"。由于正序从小到大推进，这样当前物品可以被反复加入方案中。

为什么先枚举物品再枚举容量得到的刚好是组合计数？

因为每个物品只在最外层被遍历一次。在处理物品 i 时，dp 中记录的是"用前 i 种物品能凑出各容量的方案数"。物品 i 被处理完后就不再回头，所以每种物品的选取次数是确定的，而不会出现"先选 i 后选 j"和"先选 j 后选 i"被视为不同方案的情况——这就自然得到组合计数。

状态定义和转移是什么？

定义 dp[c] = 恰好凑出容量 c 的组合方案数（对 MOD 取模）。

初始 dp[0] = 1。

对于每种物品体积 v，容量 c 从 v 到 V 正序：

text
dp[c] = (dp[c] + dp[c - v]) % MOD

代码

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:11
 * update_at: 2026-08-08 23:11
 */
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<int> dp(V + 1);
    dp[0] = 1;
    for (int i = 0; i < N; ++i) {
        int v;
        cin >> v;
        for (int c = v; c <= V; ++c)
            dp[c] = (dp[c] + dp[c - v]) % MOD;
    }
    cout << dp[V] << '\n';
    return 0;
}

复杂度

  • 时间：O(N × V)，每种物品遍历 V 个容量
  • 空间：O(V)，dp 数组大小 V+1

总结

完全背包的组合计数，先枚举物品再正序枚举容量。dp[0]=1 是基础。转移 dp[c] += dp[c-v] 本质是分类加法原理：每种"之前方案 + 当前物品"都是新方案。先物品后容量的枚举顺序天然保证了组合语义（不区分排列顺序）。