최적화 문제

여러 개의 답 중 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 부릅니다. 예를 들어 $n$개의 원소 중에서 $r$개를 순서 없이 골라내는 방법의 수를 계산하는 것은 최적화 문제가 아닙니다. 반면 $n$개의 사과 중에서 $r$개를 골라서 무게의 합을 최대화하는 문제는 최적화 문제입니다.
최적화 문제를 해결하는 가장 기초적인 방법은 완전 탐색입니다 가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문입니다.