배낭 문제

물건마다 무게와 가치가 있고 배낭이 견디는 무게에 한도가 있을 때, 가치의 합이 가장 크게 물건을 고르는 문제다. 「가치 합이 V 이상이 되게 담을 수 있는가」로 묻는 결정 문제 판은 NP-완전이다. 부분합 문제는 배낭 문제의 특수한 경우다. 숫자가 작으면 동적 계획법으로 빨리 풀리고, 최적값에 원하는 만큼 가까운 해를 다항 시간에 구하는 근사 방법도 있다. NP-완전 문제라도 다루기 쉬운 정도는 서로 다르다는 것을 보여 주는 예다.