C/C++で実装する貪欲アルゴリズム：最小コイン枚数を求めるプログラム

貪欲アルゴリズム（グリーディ法）とは、与えられた問題に対する最適解を見つけるために用いられる手法です。問題全体を一度に扱うのではなく、各段階で「その時点で最も良い選択（局所最適解）」を積み重ねていくことで、最終的に全体の最適解へ到達することを目指します。

本記事では、貪欲アルゴリズムを使って、指定された金額を作るために必要なコイン・紙幣の最小枚数を求める方法を解説します。使用できる額面は { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 } とし、これらのコイン・紙幣を何枚組み合わせれば目標の合計金額になるかを求めます。

具体例

例1

入力 : 1231
出力 : 7

解説：500ルピー紙幣2枚、100ルピー紙幣2枚、20ルピー紙幣1枚、10ルピー紙幣1枚、1ルピーコイン1枚を使用します。合計枚数は 2+2+1+1+1 = 7 枚です。

例2

入力 : 2150
出力 : 3

解説：2000ルピー紙幣1枚、100ルピー紙幣1枚、50ルピー紙幣1枚の合計3枚で表せます。

貪欲法での解き方

この問題を貪欲アルゴリズムで解く手順はシンプルです。まず、残りの金額に対して使用できる最大の額面を見つけます。次に、その額面を合計金額から差し引き、残額がゼロになるまで同じ処理を繰り返します。大きな額面から優先的に使うことで、必要な枚数を最小化できます。

アルゴリズム

入力: sum（目標金額）
coins = 0 として初期化
ステップ1: sum 未満で最大の額面を見つける
ステップ2: その額面を coins に加え、sum から差し引く
ステップ3: sum が 0 になるまでステップ2を繰り返す
ステップ4: coins の各値を出力する

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int notes[] = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };
int n = sizeof(notes) / sizeof(notes[0]);
void minchange(int sum){
    vector<int> coins;
    for (int i = n - 1; i >= 0; i--) {
        while (sum >= notes[i]) {
            sum -= notes[i];
            coins.push_back(notes[i]);
        }
    }
    for (int i = 0; i < coins.size(); i++)
        cout << coins[i] << "\t";
}
int main(){
    int n = 3253;
    cout << "The minimum number of coins/notes that sum up " << n << " is \t ";
    minchange(n);
    return 0;
}

実行結果

The minimum number of coins/notes that sum up 3253 is
2000 500 500 200 50 2 1

この出力は、2000×1枚、500×2枚、200×1枚、50×1枚、2×1枚、1×1枚の合計7枚で3253を表していることを意味します。大きな額面から順に割り当てていくだけで、自動的に最小枚数の組み合わせが得られています。

注意点：貪欲法が有効な条件

貪欲法は、{1, 2, 5, 10, 20, 50, 100, 200, 500, 2000} のように「大きな額面ほど効率的」という性質を持つ通貨体系では常に最適解を与えます。しかし、任意の額面セットでは必ずしも最適になるとは限りません。たとえば額面 {1, 3, 4} で金額6を作る場合、貪欲法では 4+1+1 の3枚になりますが、最適解は 3+3 の2枚です。このような場合は動的計画法（DP）を用いる必要があるため、扱う通貨体系の特性を確認しておくことが重要です。