纸币问题 1

题目描述

某国有 $n$ 种纸币，每种纸币面额为 $a_i$ 并且有无限张，现在要凑出 $w$ 的金额，试问最少用多少张纸币可以凑出来？

输入格式

第一行两个整数 $n,w$，分别表示纸币的种数和要凑出的金额。
第二行一行 $n$ 个以空格隔开的整数 $a_1,a_2,a_3,\dots a_n$ 依次表示这 $n$ 种纸币的面额。

输出格式

一行一个整数，表示最少使用的纸币张数。

样例 #1

样例输入 #1

6 15
1 5 10 20 50 100

样例输出 #1

2

样例 #2

样例输入 #2

3 15
1 5 11

样例输出 #2

3

提示

对于 $40\%$ 的数据，满足 $n\le 10$，$w\le 100$；
对于 $100\%$ 的数据，满足 $1\le n\le 10^3$，$1\le a_i\le w\le 10^4$。

C++实现

#include<bits/stdc++.h>
using namespace std;
int dp[100001],n,a[101010],cost,w;
int main(){
cin>>n>>w;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1;i <= w;i++){
cost = 0x3f3f3f3f;
for(int j = 1; j <= n; j++){
if(i - a[j] >= 0) cost = min(cost, dp[i - a[j]]);
}
dp[i] = cost + 1;
}
cout << dp[w];
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容