【AtCoder版！蟻本】AOJ Courseコイン問題【貪欲法】

AtCoder版！蟻本の貪欲法の例題としてあげられているAOJ Coin Changing ProblemをPythonで解いていきます。

リンク

AOJ Coin Changing Problem

Coin Changing Problem

問題文

額面がc1, c2,..., cm　円の　m　種類のコインを使って、 n 円を支払うときの、コインの最小の枚数を求めて下さい。
各額面のコインは何度でも使用することができます。

制約

・１行目に整数 n と整数 m が１つの空白区切りで１行に与えられます。
・２行目に各コインの額面が１つの空白区切りで１行に与えられます。

解答例

n, m = map(int,input().split())

coin = list(map(int,input().split()))

INF = int(1e9)

dp = [[INF] * (n+1) for i in range(m)]

for i in range(m):
    dp[i][0] = 0

for i in range(m):
    for j in range(n+1):
        if j < coin[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i][j-coin[i]] + 1)

print(dp[m-1][n])

解説

m種類の硬貨を使ってn円支払うときの、最小の硬貨の枚数を答える問題です。

値段の高い硬貨から払えばよさそうですが、硬貨の種類によっては最適とならない場合があるため動的計画法を用います。

dp[i][j]をi枚目までの硬貨でj円支払うときの硬貨の最小枚数としました。

支払う金額が硬貨の金額以上になったときに、i番目の硬貨を使わない場合と硬貨を使用する場合を比較して最小枚数を格納していきます。

dpを更新し終えたあとに該当箇所を出力すればOKでした。

AtCoder版！蟻本（初級編）の記事リンクページはこちら
ebisuke33.hatenablog.com

リンク