배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은?
- ①0－1 배낭 문제와 분할 가능 배낭 문제는 다항식 시간(polynomial-time) 문제이다.
- ②분할 가능 배낭 문제는 최적 부분 구조를 갖지만, 0－1 배낭 문제는 그렇지 않다.
- ③0－1 배낭 문제는 물건을 나눌 수 없어서 그리디(greedy) 알고리즘을 적용하여 해결할 수 있으며, 분할 가능 배낭 문제는 물건을 나눌 수 있어 동적 프로그래밍으로 해결해야 한다.
- ④분할 가능 배낭 문제는 ‘단위 무게당 가치가 가장 높은 물건을 선택’하는 방식이 항상 최적해를 보장하지만, 0－1 배낭 문제는 그렇지 않다.
선지를 골라 바로 채점해 보세요.
정답 ④
출처: 인사혁신처 공개 기출(공공데이터포털, 이용허락 제한 없음)