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