AOJ DPL1: A - Coin Changing Problem

問題

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A

問題概要

額面が { c_1, c_2, ... c_m } 円の m { (1 \leqq m \leqq 20) } 種類の硬貨を使って n { (0 \leqq n \leqq 50000) } 円を支払うときの使用する硬貨の最小枚数を求めよ。

なお各額面のコインは何度でも使用できるものとし, 与えられるコインの額面はすべて異なり, 必ず1を含むことが保証されている。

次のような入力が与えられたとき

15 6
1 2 7 8 12 50

n = 15, m = 6 で

7 円の硬貨 1 枚と 8 円の硬貨を 1 枚の合計 2 枚が支払い方の最小枚数となるので,

2

が出力すべき答えである。

解答例

指針

  • DP

解説

この問題は一見すると価値の高いコインを払えるだけ払うという操作を繰り返せば最適解が求まりそうであるが, 例に示した通り, この方法では必ずしも正しい答えを得られるとは限らない。

この問題に対しては動的計画法 (Dynamic Programming: DP) が有効である。

以下のように定義された DP テーブルを用意して小さい金額からループを回して DP テーブルを更新する。

dp[v] := 価値 v 円を支払うときに使用するコインの最小枚数

#include <iostream>
#include <algorithm>

#define INF 1e9

using namespace std;

int main() {
    int n, m, c[21];
    int dp[50001];

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }

    fill(dp, dp + 50001, INF);

    dp[0] = 0;

    for (int i = 0; i < m; i++) {
        for (int j = 0; j + c[i] <= n; j++) {
            dp[j + c[i]] = min(dp[j + c[i]], dp[j] + 1);
        }
    }

    cout << dp[n] << endl;

    return 0;
}
#!/usr/bin/env python2
# coding: utf-8

n, m = map(int, raw_input().split())
c = map(int, raw_input().split())

dp = ['inf'] * 50001
dp[0] = 0;

for i in range(m):
    for j in range(n+1):
        if j + c[i] > n:
            break
        else:
            dp[j + c[i]] = min(dp[j + c[i]], dp[j] + 1)

print dp[n]

参考文献