용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 중에서 골라 넣는다. 각 물건은 하나씩밖에 없고 나눌 수 없다. 무게의 합계가 8 이하일 때 가치 합계의 최댓값은 얼마인가?

정답: C. 10

무게 3과 5인 물건을 고르면 무게 8에 가치는 4 + 6 = 10이 되며, 이것이 최대입니다. 무게 2와 5(가치 9)나 3과 4(가치 9)도 들어가지만 10에는 미치지 못하고, 3개를 고르면 가장 가벼운 2 + 3 + 4라도 9로 용량을 넘습니다. 무게당 가치가 높은 순서로 채우는 탐욕 알고리즘에서는 무게 2와 3(가치 7)을 넣은 뒤 남은 용량 3에 들어갈 물건이 없어 7에서 멈춥니다. 동적 계획법에서는 '용량 c까지로 달성할 수 있는 최대 가치'를 물건마다 표로 갱신하여, 물건 수 n과 용량 W에 대해 O(nW)로 최적의 값을 구합니다.