그리디 알고리즘은 최종 솔루션이 전체적 의미에서 최적일 것이라는 기대에서 각 단계에서 최적(현재 단계 내) 변형을 선택하는 알고리즘입니다.
작은 예:
액면가가 다른 동전이 무한정 있고 양 S를 모아야 한다고 가정해 보겠습니다. 두 가지 특정한 경우를 생각해 봅시다. 각 경우는 탐욕스러운 알고리즘으로 해결하려고 합니다.
즉, 우리는 다음과 같이 행동할 것입니다: 각 단계에서 우리는 남은 양을 초과하지 않는 최고 액면가(단계 내 최선의 선택)의 동전을 취할 것입니다.
a) 동전 액면가를 1, 5, 10, S = 27이라고 하자.
1) 테이크 10, S: 27 -> 17
2) 테이크 10, S: 17 -> 7
3) 테이크 5, S: 7 -> 2
4) 테이크 1, S: 2 -> 1
5) 테이크 1, S:1 -> 0
그 결과 동전 5개를 획득했습니다. 독립적으로(예: 무차별 대입) 4개 이하의 동전에 대해 27점을 얻을 수 없도록 할 수 있습니다.
b) 동전의 액면가를 1, 5, 7, S = 24라고 하자.
1) 테이크 7, S: 24 -> 17
2) 테이크 7, S: 17 -> 10
3) 테이크 7, S:10 -> 3
4) 테이크 1, S: 3 -> 2
5) 테이크 1, S: 2 -> 1
6) 테이크 1, S:1 -> 0.
우리는 6개의 동전으로 점수를 얻었지만 액면가 7인 동전 2개와 액면가 5인 동전 2개인 4개의 동전으로 S를 득점할 수 있었습니다.
예제에서 알 수 있듯이 욕심 많은 알고리즘으로 문제를 해결하는 것이 항상 가능한 것은 아닙니다. 그러나 그것이 전체 최적의 답으로 이어진다면 일반적으로 동적 프로그래밍이나 다른 방법을 사용하는 것보다 쉬울 것입니다.