dpl_1_a aoj 動的計画法 コイン両替問題

DPL_1_A コイン両替問題(最小枚数)

DPL_1_A コイン両替問題(最小枚数)
Feb. 2, 2020, 1:52 p.m.

目次

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp

解説

コインの集合と支払う金額が与えれられて、支払える最小のコイ数を求める問題.
再帰的にトップダウンで計算していくと重複する計算が大量に発生するので、漸化式を立ててボトムアップで計算していく.

ベースケースとして、コインを1枚も使わない場合は支払い不可能.
なので仮に無限とする.
また、金額が0の場合はコインを1枚も使わずに支払えるので必要枚数0.

以下のテーブルは、金額が15でコインが1 2 7 8 12 50であるときの例.

1
2
3
4
5
6
7
0   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   10001   
0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  
0   1   1   2   2   3   3   4   4   5   5   6   6   7   7   8   
0   1   1   2   2   3   3   1   2   2   3   3   4   4   2   3   
0   1   1   2   2   3   3   1   1   2   2   3   3   4   2   2   
0   1   1   2   2   3   3   1   1   2   2   3   1   2   2   2   
0   1   1   2   2   3   3   1   1   2   2   3   1   2   2   2

計算量

$O(MN)$

解答1(より少ないスペース)

必要メモリ: $O(N)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define W_MAX 10000
#define INF 10001
#define N_MAX 50001
#define M_MAX 21

Int N, M;
Int COINS[M_MAX+1];
Int table[N_MAX+1];

Int min_coin() {
  loop(n,0,N+1) {
    table[n] = INF;
  }
  table[0] = 0;

  loop(m,1,M+1) {
    Int coin = COINS[m];
    loop(n,coin,N+1) {
      table[n] = min(table[n], table[n-coin] + 1);
    }
  }

  return table[N];
}

int main(void) {
  cin >> N >> M;
  COINS[0] = 0;
  loop(i,1,M+1) {
    cin >> COINS[i];
  }

  cout << min_coin() << endl;
}

解答 2

必要メモリ: $O(MN)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define W_MAX 10000
#define INF 10001
#define N_MAX 50001
#define M_MAX 21

Int N, M;
Int COINS[M_MAX+1];
Int table[M_MAX+1][N_MAX+1];

Int min_coin() {
  loop(n,0,N+1) {
    table[0][n] = INF;
  }
  loop(m,0,M+1) {
    table[m][0] = 0;
  }

  loop(m,1,M+1) {
    Int coin = COINS[m];
    loop(n,1,N+1) {
      if (n - coin < 0) {
        table[m][n] = table[m-1][n];
        continue;
      }

      table[m][n] = min(table[m-1][n], table[m][n-coin] + 1);
    }
  }

  return table[M][N];
}

int main(void) {
  cin >> N >> M;
  COINS[0] = 0;
  loop(i,1,M+1) {
    cin >> COINS[i];
  }

  cout << min_coin() << endl;
}