AOJ DPL1: A - Coin Changing Problem

競技プログラミング AOJ 動的計画法

問題

問題文

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 円を支払うときに使用するコインの最小枚数

dpテーブルは最初, 以下のように初期値を設定しておく.

{\displaystyle \begin{eqnarray} dp(i) = \left\{ \begin{array}{l} 0 \quad (i = 0) \\ INF \quad (i \neq 0) \end{array} \right. \end{eqnarray} }

DPの書き方には配るDPと貰うDPの二種類がある.

配るDPは i を見ているとき(ループカウンタが i のとき), iより大きいDPテーブルを更新していく方法.

貰うDPは i を見ているとき, iより小さいDPテーブルの値をもとに dp[i] を更新していく方法.

  • C++ (配るDP)
// submission: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3396547

#include <iostream>
#include <algorithm>

using namespace std;
 
const int INF = 1e8;
 
int main() {
    int n, m;
    int c[21];
 
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        cin >> c[i];
    }
 
    int dp[50005];
    // dpテーブルの初期化
    for (int i = 0; i < 50005; i++) {
        if (!i) { dp[i] = 0; }
        else { dp[i] = INF; }
    }
 
    for (int i = 0; i <= 50000; i++) {
        for (int j = 0; j < m; j++) {
            if ( i + c[j] > 50000 ) { continue; }
            dp[i+c[j]] = min(dp[i] + 1, dp[i+c[j]]);
        }
    }
    cout << dp[n] << endl;
 
    return 0;
}
  • C++ (貰うDP)
// submission: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3396543

#include <iostream>
#include <algorithm>

using namespace std;

const int INF = 1e8;

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

    cin >> n >> m;

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

    int dp[50005];
    // dpテーブルの初期化
    for (int i = 0; i < 50005; i++) {
        if (!i) { dp[i] = 0; }
        else { dp[i] = INF; }
    }

    for (int i = 1; i <= 50000; i++) {
        int cand = INF;
        for (int j = 0; j < m; j++) {
            if ( i - c[j] < 0 ) { continue; }
            cand = min(cand, dp[i-c[j]] + 1);
        }
        dp[i] = cand;
    }

    cout << dp[n] << endl;

    return 0;
}
  • Python3 (配るDP)
#!/usr/bin/env python3
# coding: utf-8
# submission: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3396552

n, m = map(int, input().split())
c = [ int(x) for x in input().split() ]

dp = [ float('inf') ] * 50001
dp[0] = 0

for i in range(50001):
    for j in c:
        if i+j > 50000:
            continue
        else:
            dp[i+j] = min(dp[i+j], dp[i]+1)

print (dp[n])
  • Python3 (貰うDP)
#!/usr/bin/env python3
# coding: utf-8
# submission: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3396555#1

n, m = map(int, input().split())
c = [ int(x) for x in input().split() ]

dp = [ float('inf') ] * 50001
dp[0] = 0

for i in range(1, 50001):
    cand = float('inf')
    for j in c:
        if i-j < 0:
            continue 
        else:
            cand = min(cand, dp[i-j] + 1)
    dp[i] = cand

print (dp[n])

類題

参考文献