배낭 문제

최적설계 수치해석 마지막 수정: 2026-08-01 04:58:05

1. 개요[편집]

배낭 문제 Knapsack problem
유형	조합 최적화 / 0-1 정수계획
복잡도	약 NP-난해(weakly NP-hard)
정확 알고리즘	O(nW) 동적 계획법(의사다항), 분지한정법
근사	FPTAS 존재 — O(n³/ε)
대표 상계	분수 배낭 탐욕해 = LP 완화 최적값

배낭 문제(knapsack problem)는 무게 $w_i$ 와 가치 $v_i$ 를 가진 물건 $n$ 개 중에서, 무게 합이 용량 $W$ 를 넘지 않으면서 가치 합이 최대가 되는 부분집합을 고르는 최적화 문제다.¹ 조합 최적화 교과서의 첫 장에 거의 반드시 등장하며, 카프가 1972년에 정리한 21개 NP-완전 문제 목록에도 이름을 올렸다.

이 문서가 다루는 것은 배낭 문제 특유의 복잡도 구조다. 왜 이 문제가 NP-난해인데도 $O(nW)$ 에 풀리는지(약 NP-난해와 의사다항 시간), 왜 그런 문제만 FPTAS를 가질 수 있는지, 그리고 분수 완화가 왜 그토록 좋은 상계를 주는지에 초점을 맞춘다. 정수 변수를 다루는 일반 이론은 정수계획법이, 부분 문제 재귀와 최적 부분구조 일반론은 동적 계획법이, 문제 부류 전반의 지형은 조합 최적화가, 순회 구조를 가진 대표 난제는 외판원 문제가 각각 담당한다. 여기서는 그 문서들로 넘길 것은 넘기고 배낭에만 있는 것을 판다.

2. 정식화[편집]

$x_i \in \{0,1\}$ 을 물건 $i$ 의 선택 여부라 하면 0-1 배낭 문제는 다음 정수계획으로 쓰인다.

\max \sum_{i=1}^{n} v_i x_i \quad \text{s.t.} \quad \sum_{i=1}^{n} w_i x_i \le W, \quad x_i \in \{0,1\}

제약이 부등식 딱 하나라는 점이 이 문제의 모든 특징을 만든다. 일반 정수계획의 제약 다발이 하나로 줄어들면서, 실행가능 영역이 “용량 축 하나 위의 누적”으로 정리되고 여기서 의사다항 동적 계획법이 가능해진다. 주요 변형은 다음과 같다.

변형	변수	비고
0-1 배낭	$x_i \in \{0,1\}$	표준형
유계 배낭	$0 \le x_i \le c_i$ 정수	2의 거듭제곱으로 쪼개 0-1로 환원
무한 배낭	$x_i \ge 0$ 정수	갱신 방향만 바꾸면 같은 DP
부분집합 합	$v_i = w_i$	용량을 정확히 채우기
다차원 배낭	제약 $m$ 개	강 NP-난해, FPTAS 없음
다중선택 배낭	그룹당 정확히 하나	자원 배분에 자주 등장

이 중 다차원 배낭이 선을 넘는 지점이라는 데 주목할 만하다. 제약이 두 개만 돼도 아래에서 설명할 의사다항 구조가 무너지고, 문제는 일반 정수계획의 난이도로 되돌아간다.

3. 약 NP-난해와 의사다항 시간[편집]

배낭 문제를 처음 배우면 반드시 하는 오해가 있다. ” $O(nW)$ 알고리즘이 있으니 다항 시간에 풀리는 것 아닌가? 그럼 P=NP인가?”

답은 아니다. 복잡도 이론에서 시간은 입력을 기술하는 비트 수에 대한 함수로 잰다. 용량 $W$ 는 입력에 이진수로 적히므로 길이가 $\log_2 W$ 비트다. 전체 입력 길이는 $\Theta(n \log W + n\log v_{\max})$ 규모인데, 알고리즘의 비용 $nW = n \cdot 2^{\log_2 W}$ 는 그 길이에 대해 지수적이다. 물건이 30개뿐이어도 $W = 10^{12}$ 이면 표가 $3\times 10^{13}$ 칸이라 손도 못 댄다.

이렇게 수치 파라미터의 값에 다항적이지만 그 자릿수에는 지수적인 알고리즘을 의사다항(pseudo-polynomial) 시간이라 하고, 의사다항 알고리즘을 갖는 NP-난해 문제를 약 NP-난해(weakly NP-hard)라 부른다. 반대로 외판원 문제나 3-분할, 통 채우기처럼 P=NP가 아닌 한 의사다항 알고리즘이 존재할 수 없는 문제를 강 NP-난해(strongly NP-hard)라 한다. 두 부류의 실질적 차이는 이렇다.

약 NP-난해 — 숫자가 작으면 정확히 풀린다. 어려움의 근원이 조합 구조가 아니라 숫자의 크기에 있다. 실제로 용량을 1진법(unary)으로 적어 주면 배낭 문제는 P에 속한다.
강 NP-난해 — 숫자를 작게 만들어도 여전히 어렵다. 그리고 이 부류는 FPTAS를 가질 수 없다(P=NP가 아닌 한).

이 구분이 실무에서 왜 중요하냐면, 문제를 만났을 때 “숫자를 반올림해서 작게 만들면 되지 않을까?”라는 전략이 통할지 말지를 이 한 줄이 결정하기 때문이다. 배낭은 통한다. 그 결과물이 다음 두 절이다.

4. 두 가지 동적 계획법[편집]

무게를 축으로 하는 DP. $f(i, w)$ 를 앞의 $i$ 개 물건만 써서 무게 예산 $w$ 이하로 얻을 수 있는 최대 가치라 하면

f(i,w) = \max\big(f(i-1,w),\ f(i-1,w-w_i) + v_i\big)

이고 답은 $f(n,W)$ 다. 시간·공간 모두 $O(nW)$ 이며, 물건 인덱스를 바깥 루프로 두고 무게를 내림차순으로 갱신하면 1차원 배열 하나( $O(W)$ 공간)로 끝난다. 이 내림차순이 0-1 배낭의 핵심 트릭으로, 오름차순으로 돌리면 같은 물건을 여러 번 담는 무한 배낭이 되어 버린다.²

가치를 축으로 하는 DP. 반대로 $g(i, v)$ 를 가치 $v$ 를 정확히 달성하는 최소 무게로 정의하면

g(i,v) = \min\big(g(i-1,v),\ g(i-1,v-v_i) + w_i\big)

가 되고, $g(n,v) \le W$ 인 최대 $v$ 가 답이다. 비용은 $O(nV)$ , $V = \sum_i v_i$ 이다. 두 DP는 어느 축이 작은지에 따라 골라 쓰면 된다는 점에서 대칭적인데, 결정적인 차이가 하나 있다. 무게는 제약이라 함부로 건드리면 해가 실행 불가능해지지만, 가치는 목적함수라 반올림해도 실행가능성이 깨지지 않는다. FPTAS가 가치 축에서만 나오는 이유가 정확히 이것이다.

5. FPTAS[편집]

완전 다항시간 근사 계획(FPTAS)은 임의의 $\epsilon > 0$ 에 대해 $(1-\epsilon)$ 보장을 주면서 $n$ 과 $1/\epsilon$ 모두에 다항인 시간에 도는 알고리즘이다. 배낭의 FPTAS는 놀랄 만큼 단순하다.

스케일 $K = \epsilon\, v_{\max} / n$ 을 잡는다.
가치를 $v_i' = \lfloor v_i / K \rfloor$ 로 반올림한다.
반올림한 문제를 가치 축 DP로 정확히 푼다.

각 물건에서 잃는 가치는 $K$ 미만이므로 총 손실은 $nK = \epsilon v_{\max}$ 이하다. 그런데 최적해는 적어도 가장 비싼 물건 하나는 담을 수 있으므로 $\mathrm{OPT} \ge v_{\max}$ 이고, 따라서 얻은 해는 $(1-\epsilon)\mathrm{OPT}$ 이상이다. 비용은 반올림된 가치 총합이 $O(n^2/\epsilon)$ 규모라 DP가 $O(n^3/\epsilon)$ 에 끝난다. $\epsilon = 0.01$ 이면 1% 이내 보장을 다항 시간에 받는 셈이다.

여기서 의사다항 알고리즘과 FPTAS의 관계가 드러난다. FPTAS는 “숫자를 작게 만든 뒤 의사다항 알고리즘을 돌리는 것” 이다. 그래서 의사다항 알고리즘이 없는 강 NP-난해 문제는 FPTAS도 가질 수 없다. 배낭 문제가 근사 알고리즘 교과서의 FPTAS 장 맨 앞에 늘 놓이는 이유다.

6. 분수 배낭과 상계[편집]

물건을 쪼갤 수 있다고 허용하면( $0 \le x_i \le 1$ ) 문제는 갑자기 쉬워진다. 가치밀도 $v_i/w_i$ 내림차순으로 정렬해 통째로 담다가, 용량이 모자라는 첫 물건만 쪼개 채우면 그것이 정확한 최적해다. 교환 논법으로 증명되며 비용은 정렬 $O(n \log n)$ , 선택 알고리즘을 쓰면 $O(n)$ 이다.

이 탐욕해가 중요한 이유는 그것이 곧 0-1 배낭의 LP 완화 최적값이기 때문이다. 최적 LP 해에는 쪼개진 물건이 많아야 하나(이를 분기 물건, break item이라 한다)뿐이라, 상계와 정수해의 간격이 $v_{\max}$ 이하로 좁다. 이 단츠히 상계가 분지한정법의 한계 함수로 그대로 쓰인다.

각 노드에서 LP 완화를 푸는 비용이 $O(n)$ 남짓이라 가지치기 판정이 극도로 싸다.
상계가 타이트해서 탐색 트리가 빨리 잘린다. 물건 수천 개짜리 0-1 배낭이 초 단위로 정확히 풀리는 것은 거의 전적으로 이 덕분이다.
정렬해 놓으면 최적해가 분기 물건 근처의 좁은 구간(core)에서만 정수해와 다르다는 성질이 있어, 그 구간만 정확히 푸는 코어 알고리즘이 표준 고성능 구현이다.
참고로 용량 제약을 라그랑주 승수법으로 목적함수에 올려 완화해도 얻는 상계는 LP 완화와 같다. 제약이 하나뿐인 문제에서는 두 완화가 일치한다.

한편 0-1 배낭에 탐욕법을 그대로 쓰면 최적 보장이 없다. 밀도 순 탐욕해와 “가장 비싼 물건 하나”를 비교해 더 나은 쪽을 취하면 1/2 근사가 되는데, 용량 $W$ 에 물건 두 개(가치 1짜리 작은 것 하나와 가치 $W$ 짜리 큰 것 하나)만 있는 반례에서 왜 이 보정이 필요한지 바로 보인다.

7. 응용과 파생[편집]

자원 배분 — 예산 $W$ 아래 사업 조합 선택, 광고 슬롯 배정, 연구과제 포트폴리오. 사실상 원형 그대로다.
화물 적재·창고 — 컨테이너 적재는 3차원 기하 제약이 붙어 다차원·기하 배낭으로 넘어간다.
포트폴리오 선택 — 종목 수 제한이 붙는 기수 제약(cardinality constrained) 포트폴리오는 0-1 변수를 가진 배낭형 제약을 그대로 물려받는다.
열 생성의 부문제 — 절단 재고 문제를 열 생성으로 풀 때, 새 절단 패턴을 찾는 가격 결정 부문제가 정확히 무한 배낭 문제다. 거대한 LP 하나가 매 반복 작은 배낭 문제를 호출하는 구조.
절단평면법과 커버 부등식 — 정수계획 솔버가 쓰는 대표적 유효 부등식이 배낭 제약에서 나온다. 합쳐서 용량을 넘기는 최소 집합 $C$ (minimal cover)에 대해 $\sum_{i \in C} x_i \le |C| - 1$ 이 성립하며, 여기에 리프팅을 얹은 커버 컷은 오늘날 모든 상용 MILP 솔버의 기본 장비다. 배낭이 정수계획 이론의 실험실 역할을 하는 이유.
암호 — 1978년 머클-헬만 배낭 암호는 초증가 수열을 숨긴 배낭 문제의 난해성에 기댔지만, 1980년대 초 격자 기법으로 완파됐다. NP-난해가 곧 안전을 뜻하지 않는다는 교훈으로 자주 인용된다.³

물건 수가 수십 개뿐이라면 절반씩 나눠 열거하는 중간에서 만나기(meet-in-the-middle) 기법으로 $O(2^{n/2})$ 에 정확히 풀 수도 있다. 배낭 문제는 이렇게 정확 해법·의사다항 DP·근사 계획·완화 기반 분지한정이 한 문제 위에 나란히 놓이는 드문 사례라, 조합 최적화 수업의 통과의례가 됐다.⁴

8. 관련 문서[편집]

이름의 유래는 배낭 하나 메고 떠나는 여행자가 무엇을 담을지 고르는 상황. 교과서 삽화는 대체로 도둑이 금괴와 보석 앞에서 고뇌하는 그림인데, 이 문제의 진짜 응용이 예산 편성과 화물 적재라는 걸 알고 나면 조금 김이 샌다. ↩
이 한 줄 방향을 반대로 써서 대회에서 틀리는 것은 통과의례에 가깝다. 무한 배낭을 원할 때는 오름차순, 0-1을 원할 때는 내림차순 — 외우는 것보다 “이미 갱신된 칸을 다시 참조하면 같은 물건을 또 담은 것”이라는 이유를 기억하는 편이 안전하다. ↩
최악의 경우 어렵다는 것과 내 인스턴스가 어렵다는 것은 전혀 다른 이야기다. 머클-헬만은 복호화를 위해 인스턴스에 특별한 구조(초증가 수열의 모듈러 변환)를 심어야 했고, 공격자는 바로 그 구조를 노렸다. ↩
그래서 면접 단골이기도 하다. 다만 “ $O(nW)$ 면 다항 시간 아닌가요?”라는 질문에 자신 있게 그렇다고 답하면 그 자리에서 표정이 바뀌는 것을 볼 수 있다. ↩