最小コイン交換問題とは？貪欲法で最少枚数の硬貨の組み合わせを求めるアルゴリズム

異なる額面の硬貨のリスト C(c₁, c₂, …, Cₙ) と、両替したい金額 V が与えられたとき、V をちょうど作るために必要な硬貨の枚数を最小化する問題を「最小コイン交換問題（Minimum Coin Change Problem）」と呼びます。

前提条件： 各額面の硬貨は無限に存在するものと仮定します。

問題の概要

ここでは、硬貨の種類が {1, 2, 5, 10} の場合を考えます。各額面とも無限枚あるため、指定された金額を作るときは、できるだけ少ない枚数で構成することを目指します。

例として、金額が 22 の場合は {10, 10, 2} の 3 枚を選べばよく、これが最小枚数の組み合わせです。

このアルゴリズムの計算量は O(V) です。ここで V は対象となる金額を表します。

入力と出力

Input:
金額として 47 を入力
Output:
Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

アルゴリズム

findMinCoin(value)

入力： 両替対象の金額

出力： 使用する硬貨の集合

この問題は貪欲法（グリーディ法）で解きます。基本的な流れは以下のとおりです。

1. 硬貨の集合を {1, 2, 5, 10} として用意する
2. 高い額面の硬貨から順に走査する
3. 残りの金額がその硬貨の額面以上である間、金額から硬貨を差し引き、使用リストに追加する
4. すべての額面を処理した後、使用した硬貨のリストを出力する

Begin
    coins set with value {1, 2, 5, 10}
    for all coins i as higher value to lower value do
        while value >= coins[i] do
            value := value – coins[i]
            add coins[i] in the coin list
        done
    done
    print all entries in the coin list.
End

C++ による実装例

#include<iostream>
#include<list>
#define COINS 4
using namespace std;

float coins[COINS] = {1, 2, 5, 10};

void findMinCoin(int cost) {
    list<int> coinList;

    // 高い額面から順に処理
    for(int i = COINS-1; i>=0; i--) {
        while(cost >= coins[i]) {
            cost -= coins[i];
            coinList.push_back(coins[i]); // リストに硬貨を追加
        }
    }

    list<int>::iterator it;

    for(it = coinList.begin(); it != coinList.end(); it++) {
        cout << *it << ", ";
    }
}

main() {
    int val;
    cout << "Enter value: ";
    cin >> val;
    cout << "Coins are: ";
    findMinCoin(val);
    cout << endl;
}

実行結果

Enter value: 47
Coins are: 10, 10, 10, 10, 5, 2

金額 47 に対して、10 円玉 4 枚・5 円玉 1 枚・2 円玉 1 枚の計 6 枚が選ばれており、これがこの通貨体系における最小枚数の組み合わせです。

補足：貪欲法が最適解を保証できる条件

貪欲法は「大きい額面から優先的に使う」単純な戦略ですが、これは {1, 2, 5, 10} や日本円のような正準な（canonical）通貨体系でのみ常に最適解を保証します。

例えば、硬貨が {1, 3, 4} の場合に金額 6 を作ることを考えます。

• 最適解：3 + 3 → 2 枚
• 貪欲法の結果：4 + 1 + 1 → 3 枚（非最適）

このような非正準な体系では、貪欲法は失敗する可能性があるため、動的計画法（DP）など別のアプローチを採用する必要があります。実際のアプリケーションでは、扱う通貨体系の性質を見極めてアルゴリズムを選択することが重要です。