• 현재 상황에서 가장 좋아보이는 답을 선택한다.
• 각 부분에서 최적을 선택하면 전체에서 최적이 될 것이라는 가정을 전제로 한다.
• 기본적으로 값이 큰 경우대로 극단적으로 문제를 접근한다.

예제

1. 분할 가능 배낭 문제
   • 여행가가 가지고 있는 배낭에는 담을 수 있는 무게의 최대값이 정해져있고, 일정 가치와 무게가 있는 짐들을 배낭을 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 문제
2. 최소수의 동전으로 거스름돈 내주기
   • 거스름돈을 내줄때 가장 적은 양의 동전을 내주는 문제
   • 예) 930원의 거스름돈을, 500원, 200원, 50원, 10원의 동전으로 내줄때, 500원 동전 1개 + 200원 동전 2개+ 10원 동전 3개 총 6개의 동전으로 가장 적은 양의 동전을 내줄 수 있다.

다이나믹 프로그래밍을 써야할 경우

위에 나온 예제를 이용하여서

930원의 거스름돈을 500원, 300원, 30원, 10원의 동전으로 동전의 단위가 바뀌었을 경우,

그리드 방법을 사용하여서 풀었을때

500원 동전 1개 + 300원 동전 1개 + 30원 동전 4개 + 10원 동전 1개 = 총 7개 이지만

300원 동전 3개 + 30원 동전 1개 = 총 4개의 더 작은 동전의 양으로 내줄 수 있다.