1
이 질문은 특히 동전 교환 문제를 해결하기위한 것입니다. 어떤 금액의 변경을 찾기 위해 사용 된 동전의 최적 수를 찾는 알고리즘을 알고 있으며 또한 이해하지만 이해할 수없는 것은 그러한 해결책을 찾기 위해 취한 경로라면 어떻게 "표시 할 수 있는가"입니다. 내가 부모 포인터를 사용하려고했는데, 나는 그것을 할 수있는 방법이라고 확신한다. 그러나 나는 그것을 구현할 방법을 모른다. 여기에 예제가 있습니다. 예 : 주어진 동전 명칭 : 1, 10, 25 변경 : 30 최적의 솔루션이 필요합니다 : 3 개 동전 사용 동전 : 10, 10, 10동적 프로그래밍을 사용하여 솔루션을 출력하는 좋은 방법은 무엇입니까?
내가 동적 프로그래밍 문제를 해결하기에 정말 좋은 아닙니다.
당신이 30에 대한 해결책을 찾기 위해 사용할 수있는 방법 (29)을 통해 1에 대한 최적의 솔루션을 알고 가정? – ElKamina
죄송합니다. 문제에 대한 현재 해결 방법이 배열에 보관되어 있다는 사실을 알려 드리는 것을 잊어 버렸습니다. 테이블을 만들지 않습니다. 그래서 저는 1-29의 해결책을 가지고 있습니다. 그러나 사용 된 동전의 수는 아닙니다. 동전은 아닙니다. 이것이 직관적 이어야만하는 것이 유감이지만 실제로는 그렇지 않습니다. 내 질문은 짐작합니다 : 행과 열 단위로 1에서 k까지 동전 교단으로 0에서 n까지의 양을 가진 2 차원 테이블을 구현하려면 각 셀의 값은 무엇이며 어떻게 계산합니까? – Sektrax
더 효율적으로 해결할 수 있습니다. 현재의 최적해가 파생 된 이전의 최적 해에 대한 포인터를 유지합니다. 예 : 10은 0에 대한 링크입니다. 20 링크에서 10 링크로, 30 링크에서 20 링크로 이제는 되돌아 가세요. 30의 링크는 20이므로 30-20 = 10, 20의 링크는 10-> 20-10 = 10 및 10-0 = 10입니다. 그것이 3 10을 얻는 방법입니다. – ElKamina