指定した金額を作るための最小コイン枚数を求めるアルゴリズム（C++実装付き）

問題の概要

コインのリスト C(c1, c2, …, cn) と目標金額 V が与えられたとき、V をちょうど作るために必要なコインの枚数を最小化する問題を考えます。

注意： 各種類のコインは無限枚使用できるものと仮定します。

ここでは、コインの種類として C = {1, 2, 5, 10} が与えられている場合を扱います。各コインは何度でも使えるため、目標金額に対してできるだけ少ない枚数のコインを組み合わせて選ぶことになります。たとえば金額 22 の場合は {10, 10, 2} の 3 枚が最小となります。

入力と出力

入力：必要な金額。例：48
出力：最小コイン枚数。この場合の出力は 7。
48 = 10 + 10 + 10 + 10 + 5 + 2 + 1

アルゴリズム（動的計画法）

この問題は動的計画法（DP）を用いることで効率的に解けます。「金額 i を作るのに必要な最小コイン枚数」を配列 coins[i] として記録し、金額の小さい順に計算を進めていきます。金額 i に対して各コイン c（c ≤ i）を最後に使うケースを調べ、coins[i − c] + 1 の最小値を求めればよいのです。

minCoins(coinList, n, value)

入力： 異なるコインのリスト、コインの種類数 n、目標金額 value

出力： 目標金額を作るために必要な最小コイン枚数

Begin
    if value = 0, then
       return 0
    define coins array of size value + 1, fill with ∞
    coins[0] := 0

    for i := 1 to value, do
       for j := 0 to n, do
          if coinList[j] <= i, then
             tempCoins := coins[i-coinList[j]]
          if tempCoins ≠ ∞ and (tempCoins + 1) < coins[i], then
             coins[i] := tempCoins + 1
       done
    done

    return coins[value]
End

処理の流れのポイント

• 初期化：coins[0] = 0（金額 0 には 0 枚でよい）、それ以外は無限大（∞）で埋める
• 金額 i を 1 から value まで順に走査し、使える各コインについて coins[i − coinList[j]] + 1 との大小を比較
• 到達不可能な金額は ∞ のまま残るため、答えが存在しないケースも判定可能

計算量は金額を V、コインの種類数を n とすると O(V × n) となり、貪欲法では正しい答えが得られないコイン体系でも確実に最適解を求められます。

C++による実装例

#include<iostream>
using namespace std;

int minCoins(int coinList[], int n, int value) {
    int coins[value+1];      // 金額 i に必要な最小コイン枚数を格納

    if(value == 0)
        return 0;             // 金額 0 の場合は 0 枚

    coins[0] = 0;

    for (int i=1; i<=value; i++)
        coins[i] = INT_MAX;  // 初期状態では金額 0 以外はすべて無限大

    for (int i=1; i<=value; i++) {  // 金額 1〜value まで最小枚数を求める
        for (int j=0; j<n; j++)
            if (coinList[j] <= i) {
                int tempCoins = coins[i-coinList[j]];
            if (tempCoins != INT_MAX && tempCoins + 1 < coins[i])
                coins[i] = tempCoins + 1;
        }
    }
    return coins[value];     // 目標金額に必要なコイン枚数
}

int main() {
    int coins[] = {1, 2, 5, 10};
    int n = 4, value;
    cout << "Enter Value: "; cin >> value;
    cout << "Minimum "<<minCoins(coins, n, value)<<" coins required.";
    return 0;
}

実行結果

Enter Value: 48
Minimum 7 coins required.

このように、金額 48 を入力すると「10 円硬貨 4 枚、5 円硬貨 1 枚、2 円硬貨 1 枚、1 円硬貨 1 枚」の合計 7 枚が最小枚数として正しく出力されます。