数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学用C++查找和为给定金额的最小货币张数和面值
假设我们有这样一个金额，我们需要找到不同面额的钞票的最小数量，这些钞票加起来等于给定的金额。从最高面额的钞票开始，尝试找到尽可能多的给定金额的钞票。这里假设我们有无限数量的{2000, 500, 200, 100, 50, 20, 10, 5, 2, 1}。所以如果金额是800，那么钞票将是500, 200, 100。
我们将使用贪婪算法来解决这个问题。
示例
#include<iostream>
using namespace std;
void countNotes(int amount) {
int notes[10] = { 2000, 500, 200, 100, 50, 20, 10, 5, 2, 1 };
int noteFreq[10] = { 0 };
for (int i = 0; i < 10; i++) {
if (amount >= notes[i]) {
noteFreq[i] = amount / notes[i];
amount = amount - noteFreq[i] * notes[i];
}
}
cout << "Note count:" << endl;
for (int i = 0; i < 9; i++) {
if (noteFreq[i] != 0) {
cout << notes[i] << " : " << noteFreq[i] << endl;
}
}
}
int main() {
int amount = 1072;
cout << "Total amount is: " << amount << endl;
countNotes(amount);
}输出
Total amount is: 1072 Note count: 500 : 2 50 : 1 20 : 1 2 : 1
更新于：2019年12月17日
2K+ 次浏览
广告