dynamic-programming
동전 변경 문제
수색…
합계 취득 방법 수
동전의 종류가 다르거 나 합계가 주어지면 동전을 합하여 총합을 몇 가지나 얻을 수 있습니까? coins = {1, 2, 3}
및 total = 5
라고 가정 해 봅시다. 5 가지 방법으로 합계를 구할 수 있습니다.
- 1 1 1 1 1
- 1 1 1 2
- 1 1 3
- 1 2 2
- 2 3
문제는 배낭 문제와 밀접한 관련이 있습니다. 유일한 차이점은 동전을 무제한으로 공급한다는 것입니다. 이 문제를 해결하기 위해 동적 프로그래밍을 사용할 것입니다.
우리는 2D 배열 dp [n] [total + 1]을 사용할 것입니다. 여기서 n 은 우리가 가지고있는 동전의 다른 종류입니다. 예제에서는 dp [3] [6]가 필요 합니다. 여기 DP [I] [j]가 우리가 동전에서 동전이 있다면 우리가 J를 얻을 수있는 방법의 수를 나타내는 것 [0] 동전까지 [I]. 우리가 2를 만들 수있는 방법을 여러 가지 방법으로 우리는 [1], 동전 [0]와 동전이 있다면 예를 들어 DP [1] [2] 저장합니다. 의 시작하자:
dp [0] [0] 에 대해 우리는 동전이 1 개 밖에 없다면 동전 [0] = 1 , 얼마나 많은 방법으로 0 을 얻을 수 있는지 묻고 있습니다. 대답은 1 가지 방법입니다. 우리가 동전을 전혀 가져 가지 않으면입니다. 계속해서 dp [0] [1] 은 우리가 동전 [0] 만 가지고 있다면 얼마나 많은 방법으로 1 을 얻을 수 있는가를 나타낼 것입니다. 답은 다시 1 입니다. 마찬가지로, dp [0] [2] , dp [0] [3] , dp [0] [4] , dp [0] [5] 는 1이 됩니다. 우리 배열은 다음과 같습니다.
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | | | | | | |
+---+---+---+---+---+---+---+
(3) | 2 | | | | | | |
+---+---+---+---+---+---+---+
우리가이 개 교단의 동전이 있다면 DP를 들어 [1] [0], 우리는 우리가 동전 [0] = 1, 동전 [1] = 2, 얼마나 많은 방법으로 우리가 공을 만들 수 있던 경우에 즉, 자신을 물어? 대답은 1 입니다. 동전을 전혀 가지지 않는 것입니다. 동전 [1] (2)는 현재 총보다 큰 = 이후 DP를 들어 [1] [1], (2)는 총을 얻기에 기여하지 않습니다. 따라서 2를 배제하고 동전을 사용하여 총계를 얻을 수있는 방법 수를 계산 합니다 [0] . 그러나이 값은 이미 dp [0] [1]에 저장되어 있습니다! 그래서 우리는 그 가치를 꼭 잡을 것입니다. 첫 번째 공식 :
if coins[i] > j
dp[i][j] := dp[i-1][j]
end if
dp [1] [2]의 경우, 교단 1 과 2의 동전이 있다면 얼마나 많은 방법으로 2 를 얻을 수 있습니까? 우리는 [0] [2] 다시 우리가 DP에 저장되어있는 2의 1 교단이 걸릴 수 있습니다 DP로 표시되는 1 교, 2 개 사용하여 동전을 만들 수있다 [1] [2 동전 [i]를, 어디에서 = 1 . 왜? 우리가 다음 예제를 본다면 분명해질 것입니다. dp [1] [3]의 경우, 교단 1 과 2의 동전이 있다면 얼마나 많은 방법으로 3 을 얻을 수 있습니까? 우리는 DP에 저장 한 방법으로 교단 1의 3 개 사용하여 동전을 만들 수 있습니다 [0] [3]. 이제 2의 1 단위를 취하면 총합을 구하려면 3 - 2 = 1 이 필요합니다. 교단 1 과 2 의 동전을 사용하여 1 을 얻는 방법의 수는 dp [1] [1]에 저장되며, dp [i] [j-coins [i]] 로 쓸 수 있습니다. 여기서 i = 1 입니다. 이것이 우리가 이전의 가치를 이와같이 쓴 이유입니다. 두 번째이자 마지막 공식은 다음과 같습니다.
if coins[i] <= j
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
이것은 전체 dp 배열을 채우기 위해 필요한 두 가지 수식입니다. 배열을 채우면 다음과 같이 표시됩니다.
+---+---+---+---+---+---+---+
(den)| | 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
(1) | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
+---+---+---+---+---+---+---+
(2) | 1 | 1 | 1 | 2 | 2 | 3 | 3 |
+---+---+---+---+---+---+---+
(3) | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+---+
dp [2] [5] 는 우리가 요구하는 답변을 포함 할 것입니다. 알고리즘 :
Procedure CoinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
dp[i][0] := 1
end for
for i from 0 to n
for j from 1 to (total + 1)
if coins[i] > j
dp[i][j] := dp[i-1][j]
else
dp[i][j] := dp[i-1][j] + dp[i][j-coins[i]]
end if
end for
end for
Return dp[n-1][total]
이 알고리즘의 시간 복잡도는 O(n * total)
. 여기서 n 은 우리가 가지고있는 동전의 명칭입니다.
최소 동전 수
동전의 종류가 다르거 나 합계가 주어지면 최소한의 동전을 사용하면 합계를 얻기 위해 몇 개의 동전을 사용해야합니까? 우리가 coins = {1, 5, 6, 8}
과 total = 11
을 가지고 있다고 가정하면, {5, 6}
두 개의 동전을 사용하여 합계를 구할 수 있습니다. 이것은 실제로 11 을 얻는 데 필요한 최소 동전 수입니다. 우리는 또한 동전의 무제한 공급이 있다고 가정합니다. 이 문제를 해결하기 위해 동적 프로그래밍을 사용할 것입니다.
우리는 2D 배열 dp [n] [total + 1]을 사용할 것입니다. 여기서 n 은 우리가 가지고있는 동전의 다른 종류입니다. 예를 들어 dp [4] [12]가 필요 합니다. 여기서 dp [i] [j] 는 우리가 동전 [0] 에서 동전 [i] 까지 동전을 가지고 있다면 j 를 얻기 위해 필요한 동전의 최소 개수를 나타냅니다. 예를 들어 dp [1] [2] 는 우리가 동전 [0] 과 동전 [1] 을 가지고 있다면 저장할 것이고, 2 를 만들기 위해 사용할 수있는 동전의 최소 개수는 얼마입니까? 의 시작하자:
처음에는 0 열의 경우 동전을 전혀 가져 가지 않고 0 을 만들 수 있습니다. 그래서 0 번째 컬럼의 모든 값은 0이됩니다. dp [0] [1]의 경우 , 우리는 동전의 1 개 종목, 즉 동전 [0] = 1 , 1 을 얻는 데 필요한 최소 동전 수는 얼마인가? 대답은 1 입니다. dp [0] [2]에 대해 , 우리가 1 을 가지고 있다면, 2 를 얻는 데 필요한 동전의 최소 개수는 얼마입니까? 대답은 2 입니다. 마찬가지로 dp [0] [3] = 3 , dp [0] [4] = 4 등등. 여기서 언급해야 할 것은, 만약 우리가 교단 1 의 동전을 가지고 있지 않다면, 동전 1 개 만을 사용하여 전체를 얻을 수없는 경우가있을 수 있다는 것입니다. 간단히하기 위해 예제에서 1 을 취합니다. 첫 번째 반복 후 우리의 dp 배열은 다음과 같습니다 :
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(denom)| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(5) | 1 | 0 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(6) | 2 | 0 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(8) | 3 | 0 | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
우리는 동전 [0] = 1 , 동전 [1] = 5 , 1 을 얻는 데 필요한 최소 동전 수는 얼마인가?라는 질문에 dp [1] [1] 동전 [1] 이 현재 총액보다 많으므로 계산에 영향을 미치지 않습니다. 우리는 동전 [5] 을 제외하고 동전 [0] 만을 사용하여 1 을 얻을 필요가 있습니다. 이 값은 dp [0] [1]에 저장됩니다. 그래서 우리는 그 위로부터 가치를 얻습니다. 첫 번째 공식은 다음과 같습니다.
if coins[i] > j
dp[i][j] := dp[i-1][j]
우리의 총 [1] [5],이 경우, 우리는 두 가지 방법으로 5 할 수 있습니다 DP 5가 될 때까지이 조건이 충족되어야합니다 :
- 우리는 dp [0] [5] (상단에서)에 저장되어있는 동전 5 개를 가져옵니다 [0] .
- 우리는 동전의 한 교단을 [1] (5-5) 동전 = 0 교단 [0].
이 두 가지 중 최소값을 선택하겠습니다. 그래서 dp [1] [5] = min ( dp [0] [5] , 1 + dp [1] [0] ) = 1 . 우리가 동전의 0 개 종파를 언급 한 이유는 여기에서 우리의 다음 입장에서 명백해질 것입니다.
dp [1] [6]의 경우 두 가지 방법으로 6 을 만들 수 있습니다.
- 우리는 동전 6 개를 가져 가며 [0] , 상단에 저장됩니다.
- 우리는 5의 1 개의 교단을 취할 수 있습니다, 합계를 얻으려면 6 - 5 = 1 이 필요합니다. 교단 1 과 5 의 동전을 사용하여 1 을 얻는 방법의 최소 수는 dp [1] [1]에 저장되며, dp [i] [j-coins [i]] 로 쓸 수 있습니다. 여기서 i = 1 입니다. 이것이 우리가 이전 방식으로 그 가치를 썼던 이유입니다.
우리는이 두 가지 방법 중 최소한을 취할 것입니다. 따라서 두 번째 공식은 다음과 같습니다.
if coins[i] >= j
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
이 두 공식을 사용하여 테이블 전체를 채울 수 있습니다. 최종 결과는 다음과 같습니다.
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(denom)| | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(1) | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11|
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(5) | 1 | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 2 | 3 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(6) | 2 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 4 | 2 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
(8) | 3 | 0 | 1 | 2 | 3 | 4 | 1 | 1 | 2 | 1 | 2 | 2 | 2 |
+---+---+---+---+---+---+---+---+---+---+---+---+---+
필요한 결과는 dp [3] [11]에 저장됩니다. 절차는 다음과 같습니다 :
Procedure coinChange(coins, total):
n := coins.length
dp[n][total + 1]
for i from 0 to n
dp[i][0] := 0
end for
for i from 1 to (total + 1)
dp[0][i] := i
end for
for i from 1 to n
for j from 1 to (total + 1)
if coins[i] > j
dp[i][j] := dp[i-1][j]
else
dp[i][j] := min(dp[i-1][j], dp[i][j-coins[i]])
end if
end for
end for
Return dp[n-1][total]
이 알고리즘의 런타임 복잡도는 다음과 같습니다. O (n * total) 여기서 n 은 동전의 교단 수입니다.
필요한 동전을 인쇄하려면 다음 사항을 확인해야합니다.
- 가치가 정상에서 오는 경우에, 현재 동전은 포함되지 않는다.
- 값이 왼쪽에서 나온 경우 현재 동전이 포함됩니다.
알고리즘은 다음과 같습니다.
Procedure printChange(coins, dp, total):
i := coins.length - 1
j := total
min := dp[i][j]
while j is not equal to 0
if dp[i-1][j] is equal to min
i := i - 1
else
Print(coins[i])
j := j - coins[i]
end if
end while
예를 들어 방향은 다음과 같습니다.
값은 6 , 5가 됩니다.