Dynamic Programming

dynamic-programming.py

임의의 동전 셋 coin_set = { 1, 5, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?

3

임의의 동전 셋 coin_set = { 1, 6, 10 } 에서 12를 만들기 위한 가장 적은 동전수는?

2

Dynamic Programming의 경우 그 이전의 최적화된 동전 수를 알고있다는 가정이 있어야만 가능하다.

그래서 알고리즘 내에서 1부터 N까지의 모든 해를 찾는 과정이 포람된다

1.   1 #!/usr/bin/python
     2 import time
     3 coin_string = raw_input("coin set? ").split(' ')
     4 coin_set = []
     5 for str in coin_string:
     6     coin_set.append(int(str))
     7 print coin_set
     8 N = int(raw_input("N? "))
     9 C = []
    10 INT_MAX = 65535
    11 for i in range(N+1):
    12     if i == 0:
    13         C.append(0)
    14         continue
    15     C.append(INT_MAX)
    16     for co in coin_set:
    17         if co <= i:
    18             if C[i] > 1 + C[i-co]:
    19                 C[i] = 1 + C[i-co]
    20 print C[N]