ちょうどの金額を払う硬貨の最少の枚数

解答

best[a] を「ちょうど a 円にする最少の枚数」とします。best[0] は 0、ほかは「作れない」を表す大きな数 (X + 1) で始めます。硬貨 c ごとに、a を c から X まで小さい順に見て、best[a - c] + 1 が best[a] より小さければ書き換えます。a を小さい順に見るので、同じ硬貨を何枚も使う場合も数えられます。best[X] が X + 1 のままなら作れないので -1、そうでなければ best[X] が答えです。表の大きさが X + 1、硬貨が K 種類なので、全部で O(K × X) です。

import sys

data = sys.stdin.read().split()
k, x = int(data[0]), int(data[1])
coins = list(map(int, data[2:2 + k]))

INF = x + 1
best = [INF] * (x + 1)
best[0] = 0
for coin in coins:
    for amount in range(coin, x + 1):
        if best[amount - coin] + 1 < best[amount]:
            best[amount] = best[amount - coin] + 1

print(best[x] if best[x] != INF else -1)

const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);
const k = data[0];
const x = data[1];
const coins = data.slice(2, 2 + k);

const INF = x + 1;
const best = new Array(x + 1).fill(INF);
best[0] = 0;
for (const coin of coins) {
  for (let amount = coin; amount <= x; amount++) {
    if (best[amount - coin] + 1 < best[amount]) best[amount] = best[amount - coin] + 1;
  }
}

console.log(best[x] !== INF ? best[x] : -1);

計算量

時間は O(K × X)、メモリは O(X) です。K が 10、X が 10 万なら、100 万回ほどの計算で済みます。

遅い解き方は、表を使わずに、硬貨ごとに何枚使うかの組み合わせを全部試すものです (記憶なしの再帰)。答えは合いますが、同じ残りの金額を何度も計算し直すので、組み合わせの数だけ時間がかかります。1 円から 10 円の硬貨で 10 万円を払う組み合わせは天文学的な数になり、終わりません。

大きい硬貨から使う貪欲法は速いですが、例 1 や小さい入力の 3 番 (1 円、3 円、4 円で 6 円)、4 番 (1 円、5 円、6 円、9 円で 11 円) で多すぎる枚数を答えてしまいます。7 番 (5 円と 3 円で 9 円) では、5 円を先に使うと残りの 4 円が払えず、3 円 3 枚で払えるのに -1 と答えてしまいます。

よくある間違い

• 大きい硬貨から使う貪欲法で答える。例 1 のような硬貨の並びで外れます
• 作れない金額を 0 にしておき、「0 枚で作れる」と取り違える。作れない印は大きな数 (X + 1 など) にします
• 作れないときに -1 ではなく、表に入れた大きな数をそのまま出力する
• 金額 a を大きい順に回して、同じ硬貨を 1 枚しか使えない数え方にしてしまう (それは荷物を 1 つずつしか選べない問題の書き方です)
• 再帰で書いて、X が 10 万のときに深さの上限で止まる。表を小さい金額から順に埋める書き方なら、深さの心配はありません