정의
배낭 문제(영어: Knapsack Problem)는 조합 최적화 문제의 하나로, 주어진 무게 제한이 있는 배낭에 각각의 무게와 값이 있는 물건들을 담을 때, 전체 무게가 제한을 넘지 않으면서 가치의 합이 최대가 되도록 물건을 선택하는 문제이다. 이 문제는 컴퓨터 과학 및 운용 과학(Operation Research) 분야에서 자주 다루어지며, NP-완전(NP-complete) 문제로 분류된다.
개요
배낭 문제는 여러 변형 형태를 가질 수 있으며, 대표적인 유형으로는 '분할 가능 배낭 문제(Fractional Knapsack Problem)'와 '0-1 배낭 문제(0-1 Knapsack Problem)'가 있다. 전자는 물건을 쪼개서 일부만 담을 수 있도록 허용하는 반면, 후자는 각 물건을 전부 담거나 아예 담지 않는 이진 선택을 요구한다. 이 문제는 동적 프로그래밍, 탐욕 알고리즘, 근사 알고리즘 등 다양한 기법을 통해 해결할 수 있으며, 특히 동적 프로그래밍은 0-1 배낭 문제에 대해 최적 해를 구하는 데 널리 사용된다.
또한 배낭 문제는 암호학 분야에서도 활용된다. 예를 들어, 메르클-헬맨(Merkle-Hellman) 공개키 암호 시스템은 배낭 문제의 계산적 난이도에 기반하여 설계되었다. 그러나 이 시스템은 후에 효율적인 공격 방법이 발견되어 실용성이 떨어지게 되었다.
어원/유래
'배낭 문제'라는 이름은 한정된 용량의 배낭(knapsack)에 물건을 적재하는 상황에서 유래한 것으로, 실제 여행 시 필요한 물건들을 어떻게 선택할지에 대한 직관적 상황에서 비롯되었다. 영어 단어 "knapsack"은 독일어로 "Knappsack" 또는 네덜란드어 "knapzak"에서 기원하며, '등산용 가방' 또는 '휴대용 가방'을 의미한다. 문제의 수학적 정의는 19세기 말부터 점차 형성되기 시작하였으며, 20세기 중반 이후 컴퓨터 과학 발전과 함께 본격적으로 연구되기 시작하였다.
특징
- NP-완전 문제이므로, 일반적인 경우에 대한 다항식 시간 알고리즘은 알려져 있지 않다.
- 동적 프로그래밍을 사용하면 의사 다항 시간(pseudo-polynomial time) 내에 해를 구할 수 있다.
- 탐욕 알고리즘은 분할 가능 문제에서는 최적 해를 제공하지만, 0-1 문제에서는 그렇지 않다.
- 실생활 응용 분야로는 자원 배분, 투자 포트폴리오 선택, 데이터 압축, 네트워크 전송 최적화 등이 있다.
관련 항목
- 동적 프로그래밍
- 탐욕 알고리즘
- NP-완전성
- 메르클-헬먼 암호
- 조합 최적화
- 부분집합 합 문제