배낭문제 (Knapsack Problem)
한 줄 정의: 용량 한도 안에서 가치 합이 최대가 되도록 물건을 고르는 조합최적화 문제입니다.
쉽게 풀면
무게 제한이 있는 가방에 여러 물건 중 무엇을 넣을지 고르는 상황을 떠올리면 됩니다. 물건마다 무게와 가치가 있고, 제한을 넘지 않으면서 가치의 합을 가장 크게 만드는 조합을 찾는 것이 목표입니다. 각 물건을 넣거나(1) 넣지 않는(0) 선택만 할 수 있으면 0-1 배낭문제라고 부릅니다.
왜 중요한가
예산 안에서 투자 프로젝트 고르기, 적재 용량 안에서 화물 고르기처럼 '한정된 자원으로 무엇을 선택할까'라는 질문의 가장 기본적인 수학 모형입니다. 또 열생성법이나 분해법에서 부분문제로 자주 등장하기 때문에 더 큰 최적화 모형을 이해하는 기초가 됩니다.
논문에서는 이렇게 쓰입니다
"예산 제약 하의 설비투자 대안 선택 문제를 0-1 배낭문제로 정식화하고 동적계획법으로 최적해를 구하였다."
투자 대안마다 선택 여부를 0과 1로 두고, 예산을 용량 제약으로 본 모형이라는 뜻입니다.
조금 더 깊게 보면
0-1 배낭문제는 NP-난해 문제로 알려져 있지만, 용량과 무게가 정수일 때는 용량에 비례하는 시간의 동적계획법(의사다항시간 알고리즘)으로 풀 수 있습니다. 물건을 쪼개 넣을 수 있는 분할 배낭문제는 가치/무게 비율이 큰 순서로 담는 탐욕법으로 최적해가 나옵니다. 제약이 여러 개인 다차원 배낭문제, 같은 물건을 여러 개 담을 수 있는 유계·무계 배낭문제 같은 변형도 널리 연구됩니다.
주의할 점
상자채우기 문제는 모든 물건을 최소 개수의 상자에 담는 문제이고, 배낭문제는 하나의 용량 안에서 가치를 최대화할 물건을 고르는 문제라는 점이 다릅니다. 분할 배낭문제의 탐욕법이 0-1 배낭문제에서는 최적을 보장하지 않는다는 점도 주의해야 합니다.