부분해가 전체해가 될 수 있는 문제면 사용할 수 있는 솔루션이다.
최소값을 찾는다고 할 때 위와 같은 문제면, 탐욕법이 적합하지 않다. 부분해를 따라가다가 지역적인 최소값을 찾게되지만 전체해가 되진 않기 때문이다.
위와 같이 탐욕법으로 최소값을 찾다가다 보면 전체해가 되는 문제여야 된다.
문제를 해석하고 부분해가 전체해가 되는지를 파악하는게 중요하다.
참고 문제 - 최소한의 동전으로 금액을 완성시키자
1. [10, 100, 500] 동전으로 710원 만들기
- 500 x 1 -> 210원 남음
- 100 x 2 -> 10원 남음
- 10 x 1 -> 0원
- 총 4개 사용
위와 같이 주어지면 탐욕법이 적용 되는 듯 보인다 하지만
2. [10, 30, 40, 50] 동전으로 70원 만들기
- 50 x 1 -> 20원 남음
- 40 사용불가, 30 사용불가
- 10 x 2 -> 0원
- 총 3개 사용
결과가 나오지만 최소한의 동전 사용의 목적은 달성하지 못했다.(부분해 달성, 전체해 미달성), 최소한의 동전의 개수는
- 40원 1개, 30원 1개
위와 같다. 이런 문제는 동적 계획법이 어울린다.
참고
https://www.youtube.com/watch?v=CxBYY7XTQvI