배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은? | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
배낭 문제(knapsack problem)에 대한 설명으로 옳은 것은?
1
0－1 배낭 문제와 분할 가능 배낭 문제는 다항식 시간(polynomial-time) 문제이다.
2
분할 가능 배낭 문제는 최적 부분 구조를 갖지만, 0－1 배낭 문제는 그렇지 않다.
3
0－1 배낭 문제는 물건을 나눌 수 없어서 그리디(greedy) 알고리즘을 적용하여 해결할 수 있으며, 분할 가능 배낭 문제는 물건을 나눌 수 있어 동적 프로그래밍으로 해결해야 한다.
4
분할 가능 배낭 문제는 ‘단위 무게당 가치가 가장 높은 물건을 선택’하는 방식이 항상 최적해를 보장하지만, 0－1 배낭 문제는 그렇지 않다.
해설
옳은 설명은 분할 가능 배낭 문제는 단위 무게당 가치가 높은 물건부터 고르는 탐욕법이 최적해를 보장하지만 0-1 배낭 문제는 그렇지 않다는 것이다.
0-1 배낭 문제는 물건을 쪼갤 수 없어 탐욕 선택이 남는 용량을 낭비할 수 있으므로 동적 프로그래밍으로 풀어야 한다.
- 0-1 배낭 문제는 NP-난해 문제(결정 문제는 NP-완전)로, 다항식 시간 알고리즘이 알려져 있지 않다.
- 0-1 배낭 문제도 최적 부분 구조를 가지며, 그래서 동적 프로그래밍을 적용할 수 있다.
- 탐욕 알고리즘이 맞는 쪽은 분할 가능 배낭이고, 동적 프로그래밍이 필요한 쪽은 0-1 배낭이므로 설명이 뒤바뀌었다.
오류나 개정된 내용이 보이면 알려주세요