【例9.17】货币系统

题目描述

给定 $n$ 种面值（正整数，每种可无限使用），求恰好凑出总面值 $m$ 的方案数。两种方案不同当且仅当某种面值使用张数不同。

输入：第一行 $n,m$ ，接下来 $n$ 行每行一个面值。输出：一行方案数。

样例： $n=3,m=10$ ，面值 $\{1,2,5\}$ ，输出 $10$ 。

思路

完全背包计数。设 $f[j]$ 为凑出面值 $j$ 的方案数， $f[0]=1$ 。外层按面值分层去重，内层金额正序枚举使面值可无限复用： $f[j] \leftarrow f[j]+f[j-a_i]$ 。答案为 $f[m]$ 。

参考代码

Python 版：

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#!/usr/bin/env python3
# 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-07-05 22:10
# update_at: 2026-07-05 22:10

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, m = next(data), next(data)  # n 种面值，目标金额 m
    coins = [next(data) for _ in range(n)]

    # f[j] = 恰好凑出面值 j 的方案数（组合计数，不区分顺序）
    f = [1] + [0] * m              # f[0] = 1：什么都不用是一种方案
    for c in coins:                # 每种面值只处理一遍 → 同一面值不区分排列顺序
        for j in range(c, m + 1):  # 正序扫：f[j] 可多次使用面值 c（完全背包）
            f[j] += f[j - c]

    print(f[m])


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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-10-05 07:44
 * update_at: 2026-10-05 07:44
 */

#include <iostream>
using namespace std;

const int MAXM = 10005;
const int MAXN = 105;

typedef long long ll;

ll n, m;
ll a[MAXN];     // 面值数组
ll f[MAXM];     // f[j] 表示凑出面值 j 的方案数

void read_input() {
    cin >> n >> m;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i];
    }
}

void solve() {
    f[0] = 1;                       // 什么都不选是一种方案
    for (ll i = 1; i <= n; i++) {   // 外层按面值分层，保证组合去重
        ll c = a[i];
        for (ll j = c; j <= m; j++) { // 金额正序枚举，面值可无限使用
            f[j] += f[j - c];
        }
    }
    cout << f[m] << "\n";
}

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

    read_input();
    solve();

    return 0;
}

【例9.17】货币系统

目录

题目描述

思路

参考代码