동전 변경 (동적 프로그래밍)

우리 보통 동전 변경 문제에 대해 다음과 재발의 관계 : 동전 변경 (동적 프로그래밍)

(P 우리가 바꿀 필요 d_i하는 전체 돈은 사용할 수있는 동전입니다)하지만 할 수 없습니다 우리는 이런 식으로합니다

C[p,Vi,j] = C[p,Vi,j-1]  if Vj > p 
      = C[p-Vj,Vi,j] + 1 if Vj <=p

,691 ( V 가능한 동전의 주어진 소트 세트, i 및 j이 Vj 주어진 가장 높은 값 동전되는과의 첨자가있다)

내가 쓴 것에 문제가 있습니까? 솔루션은 역동적이지는 않지만 더 효율적이지는 않습니까?

2012-10-25 Gaurav

V가 1 단위의 동전을 가지고 있다고 가정하지 않습니다. P = 7이고 V = [3, 2] 인 경우, 가치 3 동전을 2 개 얻은 다음 1 가치 3 동전과 2 가치 2 동전 대신 오류가 발생합니다. –

@LastCoder 귀하의 요지가 있습니다. 위의 해법은 우리가 1 단위의 동전을 가지고 있다고 가정합니다. 이제 다음 것은 우리가 1 단위의 동전을 받았다면 위의 것이 더 효율적인 해결책이되고 역동적 인 해결책이 될 것입니다, 그렇습니까? – Gaurav

수식에'Vi'를 어디에 사용합니까? – IVlad

이 P = 6, V = {4, 3, 1}을 고려 메모리 만 낭비. 대신 4, 1, 1을 골라야하므로 2 대신 3 동전을 골라야합니다.

2012-10-25 19:11:19 IVlad

. 이것은 내 문제를 해결합니다. – Gaurav

작성한 내용은 특정 조건에서만 작동하는 그리 디 알고리즘과 유사합니다. (How to tell if greedy algorithm suffices for finding minimum coin change? 참조). 또한

, 버전에 실제로 재발 내 Vi를 사용하지 않는, 그래서

2012-10-25 19:09:31 dfb

답변