洛谷 P2842 纸币问题 1 -普及-
题目描述
某国有 nnn 种纸币,每种纸币面额为 aia_iai 并且有无限张,现在要凑出 www 的金额,试问最少用多少张纸币可以凑出来?
输入格式
第一行两个整数 n,wn,wn,w,分别表示纸币的种数和要凑出的金额。
第二行一行 nnn 个以空格隔开的整数 a1,a2,a3,…ana_1, a_2, a_3, \dots a_na1,a2,a3,…an 依次表示这 nnn 种纸币的面额。
输出格式
一行一个整数,表示最少使用的纸币张数。
输入输出样例 #1
输入 #1
6 15
1 5 10 20 50 100
输出 #1
2
输入输出样例 #2
输入 #2
3 15
1 5 11
输出 #2
3
说明/提示
对于 40%40\%40% 的数据,满足 n≤10n\le 10n≤10,w≤100w\le 100w≤100;
对于 100%100\%100% 的数据,满足 1≤n≤1031\le n\le 10^31≤n≤103,1≤ai,w≤1041\le a_i , w\le 10^41≤ai,w≤104。
solution
动态规划:
- 1 定义公式:
- 设 f[i][j]: 如果只用前 i 种纸币,最少需要多少张才能拼成 j 元。
- 2 递推关系:
- f[i][j] = min(f[i][j], f[i][j - a[i]] + 1, f[i-1][j])
- 因为 i 只影响 i + 1,所以只需要保存一个,可以省略一个维度
递推公式 f[j] = min(f[j], f[j - a[i]] + 1)
- 3 结果
f[w]
代码
#include<iostream>
#include "unordered_map"
#include "unordered_set"
#include "stack"
#include "queue"
#include "cstring"
#include "algorithm"using namespace std;
const int N = 1e3 + 5, INF = 1e4, M = 1e4 + 5;int a[N], n, w, f[M];int main() {cin >> n >> w;for (int i = 0; i < n; i++) cin >> a[i];for (int j = 1; j <= w; j++) {f[j] = INF;for (int i = 0; i < n; i++) {if (j >= a[i]) {f[j] = min(f[j], f[j - a[i]] + 1);}}}cout << f[w];return 0;
}