- 최적 부분 구조
- 탐욕적 선택 속성
- 현재 가장 최상인 경우 선택
- 미래의 경우를 생각 안하고
- 이 경우 항상 최적해 보장 못함
- 단, 미래의 경우에 영향일 미치지 않는다면, 항상 최적해 보장
- 지금 당장의 최적이 전체의 최적해를 보장한다면
- 현재 가장 최상인 경우 선택
- 거스름돈 최적화
- 1, 5, 10, 50원 의 경우 ‘65원’ 최적해 보장
- 50, 10, 5
- 1, 5, 10, 12, 50원 의 경우 ‘65원’ 불완적 → DP 필요 ^6d4b0e
- 50, 12, 1, 1, 1
- 1, 5, 10, 50원 의 경우 ‘65원’ 최적해 보장