동적 기획 - 동전 문제

문제: 만약 우리가 액면가가 1원, 3원, 5원인 동전 몇 개를 가지고 있다면, 어떻게 가장 적은 동전으로 11원을 모을 수 있습니까?
 
동적 기획의 본질은 원래 문제를 같은 성질의 약간의 동일한 서브구조로 분해하고 최우수치를 구하는 과정에서 서브구조의 최우수치를 한 표에 기록함으로써 때때로 대량의 중복 계산이 발생하지 않도록 하는 것이다.
예를 들어 동전 조합 문제에서 11위안의 최소 동전 수를 구하려면 먼저 0위안, 1위안, 2위안을 모은 서브구조부터 분석할 수 있다.
 
만약 d(i)가 i원을 모으기 위해 필요한 최소 동전 수를 채우면
당연하다
d(1)=1원을 채우려면 액면가가 1원 이하인 동전 중에서 선택해야 하는데, 현재는 액면가가 1원인 동전만 있다
d(1) = d(0) + 1
d(2)=d(2-1)+1=2, 액면가가 2원 이하인 동전 중에서 선택하고, 요구에 부합되는 동전의 액면가는 1원이다.
d(2) = d(2-1) + 1
d(3)= d(3-3)+1=1, 액면가가 3원 이하인 동전 중에서 선택하고, 요구에 부합되는 동전의 액면가는 1원, 3원이다.
이때 두 가지 선택이 있다. 액면가 3원이 함유된 동전을 선택할지 말지.
3원짜리 동전 함유: d(3)=d(3-3)+1=1
3원짜리 동전 없음: d (3) = d (3 - 1) + 1 = d (2) + 1 = 3
자연히 양자 중 비교적 작은 값을 선택한다
순서대로 유추하다.
 
이 문제에 대해 총괄적으로 말하자면, 충분한 돈을 모아야 하는 수가 증가함에 따라
1. 우선 해당 금액보다 크지 않은 액면가를 모두 알아야 한다.
2. 각 액면가의 동전에 대해 해당 액면가의 동전을 선택할 때 필요한 동전 수를 구한다
동전 하나를 선택한 후 필요한 동전 수 +1, 필요한 동전 수 = 원래 모아야 할 동전 수 - 이 동전의 액면가, 모아야 할 동전 수가 감소하고, 줄여야 할 동전 수를 최소한 모아야 하는 원문제의 서브구조에 속하며, 이미 해답을 구했다.
3. 위에서 구한 결과에 집중하여 최소치, 즉 이 돈을 모으기 위해 필요한 최소 동전 수를 선택한다.
 
이를 통해 알 수 있듯이 모든 문제의 최우수치는 그 서브구조의 최우수를 빌려 얻을 만한 가치가 있다.
이 알고리즘의 가장 작은 서브구조의 가장 좋은 해답은 이미 알려진 것이다. 즉, 돈을 0원으로 모으려면 최소한 0개의 동전이 필요하다.
이 가장 작은 서브 구조를 이용하여, 점차적인 추이식을 통해 지정된 값이 돈을 모을 수 있는 가장 좋은 값을 구할 수 있다
 
위에서 언급한 추이식은 바로 상태 이동 방정식이다.이미 알고 있는 상태를 이용하여 끊임없이 상태 이동 방정식을 통해 해를 구하면 최우수치와 최우수해를 얻을 수 있다.
다음은 동전 조합 문제의 수학적 설명을 살펴보자.
d(i)=min{d(i-vj)+1}, 그 중에서 i-vj>=0, vj는 제j개의 동전의 액면가를 나타내고, i는 i원을 모으는 것을 나타내며, d(i)는 i원이 최소한 필요한 동전의 수를 모으는 것을 나타낸다.즉,
 

                     　　　　0  　　　　 i == 0  
min_coin_num(i) = {
                  　　　　　min{ min_coin_num( i-coin_value(j) )+1 | i-coin_value(j)>0} coin_value(j)   j       　　i > 0  

 
총 토탈value가 i일 때 모든coinvalue(j) < i의 코인 j, min {min coin num(i-coin value(j))}
 
마지막으로 이 알고리즘의python 구현은 다음과 같습니다.

#         1 、3  5       ，          11 
 2 
 3 
 4 
 5 def select_coin(coin_value, total_value):
 6     min_coin_num = [0]
 7     for i in range(1, total_value + 1):
 8         min_coin_num.append(float('inf'))
 9         for value in coin_value:
10             if value <= i and min_coin_num[i - value] + 1 < min_coin_num[i]:
11                 min_coin_num[i] = min_coin_num[i - value] + 1
12 
13     return min_coin_num
14 
15 
16 result = select_coin([1, 3, 5], 11)
17 print("coin number:" + str(result[-1]))