纸币问题 1

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

把每种纸币看作可以无限使用的物品，dp[j]=min(dp[j],dp[j-v]+1) 正序枚举金额求最少张数。

OJ: luogu

题目 ID: P2842

难度:普及-

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

日期: 2026-08-08 23:13

目录

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

    题意

    有 nn 种纸币，第 ii 种面额为 aia_i，每种无限张。给定要凑出的金额 ww（1⩽w⩽1041 \leqslant w \leqslant 10^4），求最少用多少张纸币能恰好凑出 ww。保证存在解。

    原题对象 背包含义
    一种纸币 一个可以重复使用的物品
    面额 aia_i 物品体积
    张数 物品个数
    凑出金额 ww 恰好装满容量 ww

    思路

    一句话本质： 完全背包求最少物品数——容量正序枚举，dp 初始化为 INF，唯一合法起点 dp[0]=0。

    先看最直接的暴力：

    cpp
    // brute.cpp：小数据暴力解，使用递归枚举每种纸币的使用张数，求最少总张数。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n;          // 纸币种类数
int w;          // 要凑出的金额
int a[MAXN];    // 每种纸币的面额
int answer;     // 最少张数

// dep：当前正在决定第 dep 种纸币的使用张数
// used：已经使用的纸币总张数
// remain：剩余需要凑出的金额
void dfs(int dep, int used, int remain) {
    if (dep == n + 1) {
        if (remain == 0 && used < answer)
            answer = used;
        return;
    }

    // 枚举第 dep 种纸币用 cnt 张
    int max_cnt = remain / a[dep];
    for (int cnt = 0; cnt <= max_cnt; cnt++) {
        dfs(dep + 1, used + cnt, remain - cnt * a[dep]);
    }
}

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

    cin >> n >> w;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    answer = INF;
    dfs(1, 0, w);
    cout << answer << '\n';

    return 0;
}

    这个暴力对每种纸币枚举使用张数，递归到叶子后检查剩余金额是否为 0，并更新最少张数。复杂度指数级，只适合小数据验证。

    这个暴力卡在哪里？

    对所有纸币依次决定张数，分支太多。对于 w=104w=10^4、n=103n=10^3，不可能枚举所有组合。

    能否先不看纸币种类，只关心"凑出某个金额的最少张数"？

    可以。设 dp[j]dp[j] 表示恰好凑出金额 jj 的最少张数。如果能用一张面额 vv 的纸币从金额 j−vj-v 转移到 jj，张数加 1。问题变成：从 dp[0]=0dp[0]=0 出发（凑 0 元需要 0 张），逐步推导更大的金额需要多少张。

    一张纸币可以被重复使用多次，转移时怎么体现？

    如果正序枚举 jj（从小到大），当计算 dp[j]dp[j] 时，dp[j−v]dp[j-v] 可能已经在本轮被更新过，这意味着同一种纸币的贡献可以叠加多次，正好符合"每种纸币无限张"的要求。

    什么时候能保证 dp[j]dp[j] 是最优的？

    因为所有转移都只走"加一张纸"的操作，dpdp 值沿着金额递增方向单调推进。每次用 dp[j]=min⁡(dp[j],dp[j−v]+1)dp[j] = \min(dp[j], dp[j-v]+1) 更新时，较小的 dp[j−v]dp[j-v] 一定先被算出，所以正序扫描就能得到正确答案。

    DP 公式

    设 dpjdp_j 表示恰好凑出金额 jj 所需的最少纸币张数。初始化 dp0=0dp_0 = 0，其余 dpj=+∞dp_j = +\infty。处理面额 aia_i 时：

    dpj=min⁡(dpj, dpj−ai+1)(j⩾ai) dp_j = \min(dp_j,\ dp_{j-a_i} + 1) \qquad (j \geqslant a_i)

    jj 正序枚举，允许同一种纸币重复使用。最终答案为 dpwdp_w。

    样例 DP 表格

    以样例 2 为例：n=3,w=15n=3, w=15，面额 1,5,111, 5, 11。

    处理纸币 面额 dp[0]dp[0] dp[1]dp[1] dp[5]dp[5] dp[6]dp[6] dp[10]dp[10] dp[11]dp[11] dp[12]dp[12] dp[15]dp[15]
    初始 — 0 INF INF INF INF INF INF INF
    纸币 1 1 0 1 5 6 10 11 12 15
    纸币 2 5 0 1 min⁡(5,0+1)=1\min(5,0+1)=1 min⁡(6,1+1)=2\min(6,1+1)=2 min⁡(10,5+1)=2\min(10,5+1)=2 min⁡(11,6+1)=3\min(11,6+1)=3 min⁡(12,7+1)=3\min(12,7+1)=3 min⁡(15,10+1)=3\min(15,10+1)=3
    纸币 3 11 0 1 1 2 2 min⁡(11,0+1)=1\min(11,0+1)=1 min⁡(3,1+1)=2\min(3,1+1)=2 min⁡(3,4+1)=3\min(3,4+1)=3

    答案 dp[15]=3dp[15] = 3（例如 1+5+11 的任意 3 张组合）。

    代码

    cpp
    #include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
const int MAXW = 10005;
const int INF = 0x3f3f3f3f;

int n;                // 纸币种类数
int w;                // 要凑出的金额
int a[MAXN];          // 每种纸币的面额
int dp[MAXW];         // dp[j] = 凑出金额 j 最少需要的纸币张数

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

void solve() {
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        // 完全背包正序枚举，每种纸币可以无限使用。
        for (int j = a[i]; j <= w; j++) {
            dp[j] = min(dp[j], dp[j - a[i]] + 1);
        }
    }

    cout << dp[w] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

    复杂度

    • 时间复杂度：O(nw)O(nw)
    • 空间复杂度：O(w)O(w)

    总结

    这题是完全背包求最小值的标准模板。关键点：

    • dp 初始化为 INF，dp[0]=0
    • 正序枚举金额，允许同种纸币重复使用
    • 最终转移：dp[j]=min⁡(dp[j],dp[j−v]+1)dp[j] = \min(dp[j], dp[j-v]+1)

    与完全背包计数题（纸币问题 2、3）相比，这里求的是 最小值，初始化不同但转移思想一致。