資料結構
網路
關係資料庫管理系統(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+ 次瀏覽
廣告