배낭 문제

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 정의
3. 계산 복잡도
4. 해법
5. 응용
6. 변형 문제
참조

1. 개요

배낭 문제는 주어진 용량 내에서 물건들의 가치 합을 최대화하는 조합을 찾는 조합 최적화 문제이다. 0-1 배낭 문제, 제한된 배낭 문제, 무제한 배낭 문제 등 다양한 변형이 존재하며, 각 품목의 복사본 수, 목표 수, 배낭 수에 따라 문제가 달라진다. 0-1 배낭 문제는 각 물품을 담을지 말지를 결정하는 가장 기본적인 형태로, 동적 프로그래밍, 재귀적 해법, 메모이제이션, 중간 만남, 탐욕 알고리즘, 근사 알고리즘 등 다양한 해법이 사용된다. 배낭 문제는 자원 할당, 투자 포트폴리오 구성, 암호 시스템, 시험 문제 출제 등 다양한 분야에 응용된다. 다차원 배낭 문제, 다중 배낭 문제, 이차 배낭 문제, 온라인 배낭 문제 등 다양한 변형 문제들이 존재한다.

더 읽어볼만한 페이지

동적 계획법 - 차원의 저주
차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다.
동적 계획법 - 비터비 알고리즘
비터비 알고리즘은 잡음이 있는 통신 링크 상에서 길쌈 부호 해독에 사용되며, 확률과 관련된 극대화 문제에 동적 계획법을 적용하는 표준 용어로, 상태 기계를 기반으로 은닉 마르코프 모델에서 가장 가능성 높은 상태 시퀀스를 찾는 데 활용되어 통신, 자연어 처리, 생물정보학 등 다양한 분야에 적용되고 개선 방법이 연구되고 있다.
조합 최적화 - A* 알고리즘
A* 알고리즘은 가중치 그래프에서 시작 노드부터 목표 노드까지 최소 비용 경로를 찾는 정보 탐색 알고리즘으로, 경로 비용과 목표까지 추정 비용의 합을 최소화하여 경로를 탐색하며 내비게이션, 게임 AI 등에 활용된다.
조합 최적화 - 정수 계획법
정수 계획법은 선형 계획법의 한 분야로, 해가 정수 값을 가져야 하는 제약 조건이 추가된 최적화 문제이며, 다양한 분야에 응용되고 정확한 알고리즘 또는 휴리스틱 방법을 통해 해결할 수 있다.
NP-완전 문제 - 지뢰 찾기
지뢰 찾기는 격자 형태 지뢰밭에서 지뢰를 피해 안전한 칸을 모두 여는 퍼즐 비디오 게임으로, 칸을 열어 지뢰 유무를 확인하며, 윈도우 탑재를 통해 대중화되었고 NP-완전 문제로 분류된다.
NP-완전 문제 - 스도쿠
스도쿠는 9x9 칸에 1부터 9까지의 숫자를 채워 넣는 퍼즐로, 각 가로줄, 세로줄, 3x3 칸에 숫자가 중복 없이 들어가야 하며, 레온하르트 오일러의 라틴 방진을 기반으로 다양한 변형과 응용 연구가 진행되고 있다.

배낭 문제
문제 개요
분야	조합 최적화
성격	NP-완전
변수
입력	항목 수 (n) 각 항목의 가치 (vᵢ) 각 항목의 무게 (wᵢ) 배낭 용량 (W)
제약 조건	배낭에 담긴 항목의 총 무게는 배낭 용량(W)을 초과할 수 없음
목표	배낭에 담긴 항목의 총 가치를 최대화
문제 유형
종류	0-1 배낭 문제 (각 항목은 한 번만 담을 수 있음) 유계 배낭 문제 (각 항목은 정해진 횟수만큼 담을 수 있음) 무계획 배낭 문제 (각 항목은 무제한으로 담을 수 있음)
관련 문제	분할 문제 부분집합 합 문제
해결 방법
최적 해법	동적 계획법 분기 한정법
근사 해법	욕심쟁이 알고리즘

2. 정의

배낭 문제는 주어진 아이템 집합과 각 아이템의 무게, 가치, 그리고 배낭의 용량이 주어졌을 때, 배낭의 용량을 초과하지 않으면서 가치의 합을 최대화하는 아이템의 부분집합을 찾는 최적화 문제이다.

품목의 집합을 $I=\{1,2,\cdots,N\}$ 라고 하고, 각 품목 $i \in I$ 의 무게를 $w_i$ , 가치를 $v_i$ 라고 하자. 배낭이 담을 수 있는 최대 무게, 즉 용량을 $W$ 라고 할 때, 배낭 문제는 일반적으로 다음과 같이 수학적으로 표현될 수 있다.

목표: 총 가치 $\sum_{i \in I}v_i x_i$ 를 최대화한다.
제약 조건: 총 무게 $\sum_{i \in I} w_i x_i \leq W$ 를 만족해야 한다.
변수 조건: $x_i$ 는 품목 $i$ 를 배낭에 넣는 개수를 나타내며, 일반적으로 음이 아닌 정수 ( $x_i \in \mathbb{N}$ , 즉 0, 1, 2, ...)이다.

:

\begin{array}{lll}\max & \sum_{i \in I}v_i x_i & \\\mathrm{s.t.} & \sum_{i \in I} w_i x_i \leq W & \\& x_i \in \mathbb{N} & (\forall i \in I)\end{array}

문제의 조건에 따라 각 품목을 하나만 넣거나(0-1 배낭 문제), 특정 개수 이하로 넣거나(제한된 배낭 문제), 개수 제한 없이 넣을 수 있는(무제한 배낭 문제) 등 다양한 변형이 존재한다.

2. 1. 0-1 배낭 문제

가장 흔하게 접하는 배낭 문제는 각 품목의 개수

x_i

를 0 또는 1로 제한하는 0-1 배낭 문제이다. 이 문제는 1부터

n

까지 번호가 매겨진

n

개의 품목이 주어지고, 각 품목은 무게

w_i

와 가치

v_i

를 가질 때, 최대 무게 용량

W

를 넘지 않으면서 가치의 총합이 최대가 되도록 품목을 선택하는 문제이다.

수학적으로는 다음과 같이 표현할 수 있다.

목표: $\sum_{i=1}^n v_i x_i$ 를 최대화한다.
제약 조건: $\sum_{i=1}^n w_i x_i \leq W$ 이고 $x_i \in \{0,1\}$ 이다.

여기서

x_i

는 품목

i

를 배낭에 넣을지 말지를 결정하는 변수로, 1이면 넣는 것을 의미하고 0이면 넣지 않는 것을 의미한다. 즉, 각 품목은 배낭에 넣거나 넣지 않거나 둘 중 하나의 선택만 가능하다.

이를 더 간결하게 표현하면 다음과 같다.

:

\begin{array}{lll}\max & \sum_{i \in I}v_i x_i & \\\mathrm{s.t.} & \sum_{i \in I} w_i x_i \leq W & \\& x_i \in \{0,1\} & (\forall i \in I)\end{array}

2. 2. 제한된 배낭 문제

'''제한된 배낭 문제'''('''BKP''')는 각 품목 ''i''를 최대 ''c''개까지만 선택할 수 있도록 제한하는 문제이다.^[1] 이는 각 품목을 하나만 선택할 수 있는 0-1 배낭 문제의 제한을 완화한 것이다.

1부터 ''n''까지 번호가 매겨진 ''n''개의 품목 집합이 있고, 각 품목 ''i''는 무게 ''w_i''와 가치 ''v_i''를 가지며, 배낭의 최대 무게 용량은 ''W''이다. 이때, 넣을 품목 ''i''의 개수를 ''x_i''라고 하면, 문제는 다음과 같이 정의된다.

목표: $\sum_{i=1}^n v_i x_i$ (총 가치)를 최대화한다.
조건: $\sum_{i=1}^n w_i x_i \leq W$ (총 무게는 용량 이하) 이고, $x_i \in \{0, 1, 2, \dots, c\}$ (각 품목의 개수는 0개 이상 ''c''개 이하의 정수)이다.

2. 3. 무제한 배낭 문제

'''무제한 배낭 문제'''(Unbounded Knapsack Problem|언바운디드 냅색 프라블럼^eng, '''UKP''')는 각 품목을 선택할 수 있는 개수에 제한이 없는 배낭 문제이다. 즉, 각 품목의 복사본 수에 대한 상한을 두지 않는다.

수학적으로는 다음과 같이 공식화할 수 있다. ''n''개의 품목이 있고, 각 품목 ''i''는 무게

w_i

와 가치

v_i

를 가진다. 배낭의 최대 허용 무게는 ''W''이다. 이때, 배낭에 담을 품목 ''i''의 개수를

x_i

라고 하면, 목표는 다음과 같다.

총 가치 $\sum_{i=1}^n v_i x_i$ 를 최대화한다.
조건: 총 무게 $\sum_{i=1}^n w_i x_i \leq W$ 를 만족해야 하며, 각 품목의 개수 $x_i$ 는 음이 아닌 정수 ( $x_i \in \mathbb{N}$ , 즉 0, 1, 2, ...)여야 한다.

이는 각 품목을 0개 또는 1개만 선택할 수 있는 0-1 배낭 문제나, 선택 가능한 개수가 특정 정수(c)로 제한되는 제한된 배낭 문제와는 구별된다.

3. 계산 복잡도

배낭 문제는 컴퓨터 과학 분야에서 다양한 계산 복잡도 측면 때문에 중요한 연구 대상이다.

핵심적으로 배낭 문제의 결정 문제 형태("주어진 무게 한도 ''W''를 넘지 않으면서 최소 ''V'' 이상의 가치를 얻을 수 있는가?")는 NP-완전 문제로 분류된다.^[9]^[10] 이는 모든 경우에 대해 다항 시간 내에 최적해를 찾는 효율적인 알고리즘이 현재까지 알려져 있지 않음을 의미한다. 또한, 주어진 해가 최적인지를 다항 시간 내에 검증하는 문제 역시 co-NP-완전으로 알려져 있어 쉽지 않다.

하지만 배낭 문제가 항상 해결 불가능한 것은 아니다. 동적 계획법을 이용하면 의사 다항 시간 안에 최적해를 구할 수 있으며, 최적해에 근사하는 해를 다항 시간 내에 찾는 완전 다항 시간 근사 알고리즘(FPTAS)도 존재한다. 실제로 발생하는 많은 문제나 특정 분포를 따르는 무작위 문제들은 정확하게 해결될 수 있는 경우도 있다.^[11]

어떤 유형의 배낭 문제가 특별히 해결하기 어려운지에 대한 연구는 계속 진행 중이며,^[9]^[10] 이는 메르클-헬만 배낭 암호 시스템과 같은 공개 키 암호화 시스템의 안전성 연구와도 연관된다.^[11] 어려운 문제 인스턴스의 특성을 이해하는 것은 알고리즘 성능 개선과 특정 문제에 대한 최적의 해결 전략 선택에 기여할 수 있다.

3. 1. 결정 문제 vs 최적화 문제

배낭 문제에는 크게 두 가지 형태가 있다. 하나는 '''결정 문제'''이고 다른 하나는 '''최적화 문제'''이다.

배낭 문제의 결정 문제 형태는 "주어진 무게 제한 ''W''를 초과하지 않으면서 최소 ''V'' 이상의 가치를 얻을 수 있는가?"라는 질문에 답하는 것이다. 이 결정 문제는 NP-완전 문제로 알려져 있다.^[9]^[10] 이는 현재까지 모든 경우에 대해 빠르고 정확하게 답을 찾는 다항 시간 알고리즘이 알려져 있지 않다는 것을 의미한다. 또한, 주어진 해가 최적인지 (즉, 더 큰 가치를 갖는 해가 없는지)를 다항 시간 내에 확인하는 알고리즘도 알려져 있지 않으며, 이 문제는 co-NP-완전이다.

반면, '''최적화 문제'''는 "주어진 무게 제한 ''W'' 내에서 얻을 수 있는 최대 가치를 가지는 해를 구하라"는 문제이다. 결정 문제가 NP-완전이기 때문에, 이 최적화 문제 역시 NP-난해(NP-hard) 문제에 속한다.

결정 문제와 최적화 문제 사이에는 밀접한 관계가 있다. 만약 결정 문제를 해결하는 다항 시간 알고리즘이 존재한다면, 이 알고리즘을 반복적으로 사용하여 최적화 문제의 최대 가치를 다항 시간 내에 찾을 수 있다. 반대로, 최적화 문제의 최적값을 다항 시간 내에 찾는 알고리즘이 있다면, 그 결과값을 이용해 결정 문제에 다항 시간 내에 답할 수 있다. 따라서 두 문제의 버전은 비슷한 난이도를 가진다고 볼 수 있다.

3. 2. P vs NP 문제와의 관계

배낭 문제의 결정 문제 형태, 즉 ''주어진 무게 한도 W를 넘지 않으면서 최소 V 이상의 가치를 얻을 수 있는가?''를 묻는 문제는 NP-완전 문제에 속한다.^[9]^[10] 이는 현재까지 알려진 바로는 모든 경우에 대해 다항 시간 안에 정확한 해를 찾는 효율적인 알고리즘이 존재하지 않음을 의미한다. 만약 P=NP 가 참이라면 NP-완전 문제인 배낭 문제 역시 다항 시간 안에 해결될 수 있겠지만, 현재 학계에서는 P≠NP일 것으로 추정하고 있다.

또한, 주어진 해가 최적의 해인지, 즉 더 높은 가치 ''V''를 갖는 다른 해가 없는지를 확인하는 문제 역시 다항 시간 알고리즘이 알려져 있지 않다. 이 문제는 Co-NP-완전 문제에 해당한다.

결정 문제와 최적화 문제 사이에는 밀접한 관계가 있다. 만약 결정 문제를 다항 시간 안에 풀 수 있는 알고리즘이 있다면, 이 알고리즘을 반복적으로 사용하여 최적화 문제의 최대 가치를 다항 시간 안에 찾을 수 있다. 반대로, 최적화 문제의 최적값을 다항 시간 안에 찾는 알고리즘이 있다면, 그 결과값을 이용해 결정 문제를 다항 시간 안에 해결할 수 있다. 따라서 배낭 문제의 결정 버전과 최적화 버전은 계산 복잡성 측면에서 유사한 난이도를 가진다고 볼 수 있다.

비록 NP-완전 문제이지만, 배낭 문제를 해결하기 위한 다양한 접근법이 연구되었다. 동적 계획법을 이용한 의사 다항 시간 알고리즘이 존재하며, 이를 활용한 완전 다항 시간 근사 알고리즘 (FPTAS)도 개발되어 있다. 실제 상황에서 발생하는 많은 배낭 문제 사례나 특정 분포를 따르는 무작위 사례들은 정확하게 해결될 수 있기도 하다.^[11]

배낭 문제의 어려움은 입력 값의 형태에 따라서도 달라진다. 물건들의 무게와 가치가 정수로 주어지는 경우에는 약한 NP-완전(weakly NP-complete)이지만, 유리수로 주어지는 경우에는 강한 NP-완전(strongly NP-complete)이 된다.^[12] 하지만 유리수 입력의 경우에도 여전히 완전 다항 시간 근사 알고리즘을 적용하는 것은 가능하다.

컴퓨터 과학자들은 어떤 종류의 배낭 문제 인스턴스가 특별히 해결하기 어려운지 연구하고 있으며,^[9]^[10] 이러한 연구는 메르클-헬만 배낭 암호 시스템과 같은 공개 키 암호화 시스템 개발에도 영향을 미쳤다. 어려운 인스턴스의 특성을 파악하는 것은 문제 해결 전략을 개선하고 알고리즘 선택에 도움을 줄 수 있다.^[11]

3. 3. 실수 가중치 문제

배낭 문제의 어려움은 입력 형식에 따라 달라진다. 가중치와 이익이 정수로 주어지면 약한 NP-완전이지만, 유리수나 실수로 주어지면 강한 NP-완전이 된다.^[12] 이는 유리수나 실수 입력이 정수 입력보다 문제를 더 어렵게 만든다는 것을 의미한다. 그러나 유리수 가중치와 이익의 경우에도 여전히 완전 다항 시간 근사 알고리즘은 존재하여 근사해를 효율적으로 찾는 것은 가능하다.^[12]

문제의 요소가 실수 또는 유리수인 경우, 문제의 계산 복잡도 하한을 분석하기 위해 결정 트리 모델이나 실수 RAM 모델과 같은 다른 계산 모델이 사용되기도 한다.^[16] 이러한 모델들은 실수 연산을 포함하여 문제의 이론적 한계를 연구하는 데 도움을 준다.

4. 해법

배낭 문제를 해결하기 위해 동적 계획법 접근 방식,^[18] 분기 한정법 접근 방식,^[19] 또는 두 접근 방식을 결합한 하이브리드 방식^[11]^[20]^[21]^[22] 등 여러 알고리즘을 사용할 수 있다. 이 외에도 문제의 특성이나 요구되는 해의 정확도에 따라 중간 만남 기법, 탐욕 알고리즘, 근사 알고리즘 등 다양한 방법들이 연구되고 적용된다. 배낭 문제는 NP-완전 문제로 알려져 있어 모든 경우에 대해 다항 시간 내에 최적해를 찾는 것은 어렵다고 여겨지지만, 특정 조건 하에서는 동적 계획법 등을 통해 최적해를 구하거나, 근사 알고리즘을 통해 효율적으로 최적해에 가까운 해를 구할 수 있다.

4. 1. 동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic programming)은 배낭 문제를 해결하는 가장 대표적인 접근 방식 중 하나이다. 이 방법은 주어진 문제를 더 작은 여러 개의 하위 문제(subproblem)로 나누어 풀고, 그 해들을 결합하여 원래 문제의 최적해를 구하는 전략을 사용한다. 특히 0-1 배낭 문제와 같이 각 물건을 한 번만 사용하거나 사용하지 않는 경우, 그리고 물건 종류별 개수에 제한이 없는 '''무제한 배낭 문제'''(Unbounded Knapsack Problem, UKP)에 대해 의사 다항 시간(pseudo-polynomial time) 내에 최적해를 찾을 수 있다.

'''무제한 배낭 문제'''의 경우, 각 종류의 물건을 원하는 만큼 사용할 수 있다. 무게

w'

까지의 배낭에서 최대 가치를 얻는 문제의 해

m[w']

는 다음과 같은 점화식으로 표현될 수 있다.

$m[0]=0$ (무게 0일 때 가치는 0)
$m[w]=\max_{i: w_i \le w} (v_i+m[w-w_i])$ (무게 $w$ 에서의 최대 가치는, 무게 $w_i$ 인 물건 $i$ 를 하나 넣고 남은 무게 $w-w_i$ 에서의 최대 가치 $m[w-w_i]$ 에 물건 $i$ 의 가치 $v_i$ 를 더한 값들 중 가장 큰 값이다.)

이 방식은

m[0]

부터

m[W]

까지 순서대로 계산하며, 각

m[w]

를 계산할 때 최대

n

개의 물건을 고려하므로, 총 시간 복잡도는

O(nW)

(빅 오 표기법)가 된다. 여기서

n

은 물건 종류의 수이고,

W

는 배낭의 최대 허용 무게이다.

'''0-1 배낭 문제'''에서도 유사한 동적 계획법 접근 방식을 사용한다. 이 경우, 각 물건은 최대 한 번만 선택할 수 있다.

m[i,w]

를 첫

i

개의 물건(1번부터

i

번까지)만을 고려했을 때, 무게 합이

w

를 넘지 않도록 배낭에 담아 얻을 수 있는 최대 가치 합으로 정의한다.

m[i,w]

는

i

번째 물건을 포함하지 않는 경우(

m[i-1, w]

)와 포함하는 경우(

m[i-1, w-w_i] + v_i

, 단

w_i \le w

) 중 더 큰 가치를 선택하여 결정된다. 이 방법 역시 테이블을 채워나가며 계산하며, 시간 복잡도와 공간 복잡도 모두

O(nW)

이다.

동적 계획법 해법의 시간 복잡도

O(nW)

는 의사 다항 시간 복잡도이다. 이는 배낭 문제가 NP-완전 문제라는 사실과 모순되지 않는다. 왜냐하면 문제의 입력 크기는 물건의 개수

n

과 각 물건의 무게/가치, 그리고 배낭 용량

W

를 표현하는 데 필요한 비트 수(예:

\log W

)에 비례하는데,

O(nW)

는

W

값 자체에 의존하기 때문이다. 즉,

W

가 입력 크기에 대해 지수적으로 커질 수 있으므로 다항 시간 알고리즘은 아니다. 이러한 특성 때문에 배낭 문제는 약하게 NP-완전한(weakly NP-complete) 문제로 분류된다.

동적 계획법은 일반적으로 테이블을 채우는 반복적인 방식으로 구현되지만, 재귀적 방식에 메모이제이션 기법을 적용하여 구현할 수도 있다. 이 방법들은 필요한 부분 문제만 계산하여 효율성을 높일 수 있다.

4. 1. 1. 재귀적 해법

0-1 배낭 문제에 대한 동적 계획법 해법은 의사 다항 시간 내에 실행될 수 있다. 각 물건의 무게

w_1,\,w_2,\,\ldots,\,w_n

와 배낭의 최대 허용 무게

W

가 모두 양의 정수라고 가정하자. 이때,

m[i,w]

를 첫

i

개 물건(1번부터

i

번까지)을 고려했을 때, 무게 합이

w

를 넘지 않도록 배낭에 담아 얻을 수 있는 최대 가치 합으로 정의한다.

m[i,w]

는 다음과 같은 재귀적 관계로 정의할 수 있다. '''(정의 A)'''

기저 조건: $m[0,\,w]=0$ (고려할 물건이 없으면 가치는 0이다.)
$i$ 번째 물건을 담을 수 없는 경우: 만약 $w_i > w$ 이면, $m[i,\,w]=m[i-1,\,w]$ ( $i$ 번째 물건은 현재 용량 $w$ 를 초과하여 담을 수 없으므로, $i-1$ 번째까지 고려한 최적해와 같다.)
$i$ 번째 물건을 담을 수 있는 경우: 만약 $w_i \leqslant w$ 이면, $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)$ ( $i$ 번째 물건을 담지 않는 경우의 가치 $m[i-1,\,w]$ 와 담는 경우의 가치 $m[i-1,w-w_i]+v_i$ 중 더 큰 값을 선택한다.)

문제의 최종 해답은

m[n,W]

를 계산하여 얻는다. 이 계산을 효율적으로 수행하기 위해, 이미 계산된

m[i,w]

값을 표(테이블)에 저장하여 중복 계산을 피하는 동적 계획법 기법을 사용한다.

다음은 반복문을 이용한 동적 계획법의 의사 코드이다.

```c

// 입력:

// 값 (배열 v)

// 무게 (배열 w)

// 물건 개수 (n)

// 배낭 용량 (W)

// 가정: 배열 v와 w는 인덱스 1부터 시작.

배열 m[0..n, 0..W];

for j from 0 to W:

m[0, j] := 0

for i from 1 to n:

m[i, 0] := 0

for i from 1 to n:

for j from 1 to W:

if w[i] > j: // i번째 물건이 현재 용량 j보다 무거움

m[i, j] := m[i-1, j]

else: // i번째 물건을 넣을지 말지 결정

m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

// 최종 결과는 m[n, W]

```

이 해법은

O(nW)

의 시간 복잡도와

O(nW)

의 공간 복잡도를 가진다. 최종 값

m[n,W]

만 필요하다면, 표의 마지막 두 행만 저장하여 공간 복잡도를

O(W)

로 줄일 수 있다.

그러나 위의 반복적 방식은 실제로는 필요하지 않은

m[i,w]

값까지 모두 계산할 수 있다. '''정의 A'''의 재귀적 구조를 직접 활용하고 메모이제이션(memoization) 기법을 적용하면, 필요한 계산만 수행하는 재귀적 해법을 구현할 수 있다. 이 방식은 계산된 값을 저장해두었다가 다시 필요할 때 조회하여 중복 계산을 방지한다.

다음은 메모이제이션을 사용한 재귀적 해법의 의사 코드이다.

```c

// 입력:

// 값 (배열 v)

// 무게 (배열 w)

// 물건 개수 (n)

// 배낭 용량 (W)

// 가정: 배열 v와 w는 인덱스 1부터 시작.

배열 value[0..n, 0..W] // 계산된 값을 저장할 배열 (메모)

모든 value[i, j]를 -1로 초기화 (아직 계산되지 않았음을 의미)

function m(i, j): // i개의 물건으로 용량 j를 채우는 최대 가치 계산

if i == 0 or j <= 0:

return 0 // 기저 조건

if value[i, j] != -1: // 이미 계산된 값이면 반환

return value[i, j]

// i번째 물건을 넣지 않는 경우의 가치 계산 (필요시 재귀 호출)

// m(i-1, j)를 먼저 계산 (value[i-1, j]가 -1이면 재귀 호출 발생)

if value[i-1, j] == -1:

m(i-1, j)

res := value[i-1, j] // 계산된 값 사용

// i번째 물건을 넣는 경우의 가치 계산 (넣을 수 있는 경우)

if w[i] <= j:

// m(i-1, j-w[i]) 계산 (필요시 재귀 호출)

if value[i-1, j-w[i]] == -1:

m(i-1, j-w[i])

res := max(res, value[i-1, j-w[i]] + v[i]) // 계산된 값 사용

value[i, j] := res // 계산 결과 저장

return res

// 최종 결과 계산 시작

최종값 := m(n, W)

```

이 재귀적 해법의 시간 복잡도는 상태 공간의 크기에 따라

O(nW)

와

O(2^n)

사이가 된다. 실제 계산되는 상태의 수가 적을 경우 반복적 방식보다 효율적일 수 있다.

예를 들어, 10개의 물건(

n=10

)과 무게 제한 67(

W=67

)이 주어졌다고 하자.

\begin{align}&w = [23, 26, 20, 18, 32, 27, 29, 26, 30, 27] \\&v = [505, 352, 458, 220, 354, 414, 498, 545, 473, 543] \\\end{align}

메모이제이션을 사용한 재귀 함수

m(10, 67)

을 호출하면, 모든

(i, j)

조합을 계산하는 대신 필요한 부분 문제들만 풀게 된다. 예를 들어,

m(10, 67)

을 계산하기 위해

m(9, 67)

과

m(9, 67-w_{10}) = m(9, 40)

이 호출되고, 이 과정이 재귀적으로 반복된다. 최종적으로

m(10, 67) = 1270

이라는 결과를 얻는다.

\begin{align}&m(10, 67) = 1270\\&m(9, 67) = 1270, m(9, 40) = 678\\&m(8, 67) = 1270, m(8, 40) = 678, m(8, 37) = 545\\&m(7, 67) = 1183, m(7, 41) = 725, m(7, 40) = 678, m(7, 37) = 505\\&m(6, 67) = 1183, m(6, 41) = 725, m(6, 40) = 678, m(6, 38) = 678, m(6, 37) = 505\\&m(5, 67) = 1183, m(5, 41) = 725, m(5, 40) = 678, m(5, 38) = 678, m(5, 37) = 505\\&m(4, 67) = 1183, m(4, 41) = 725, m(4, 40) = 678, m(4, 38) = 678, m(4, 37) = 505, m(4, 35) = 505\\&m(3, 67) = 963, m(3, 49) = 963, m(3, 41) = 505, m(3, 40) = 505, m(3, 38) = 505, m(3, 37) = 505, m(3, 35) = 505, m(3, 23) = 505, m(3, 22) = 458, m(3, 20) = 458\\&m(2, 67) = 857, m(2, 49) = 857, m(2, 47) = 505, m(2, 41) = 505, m(2, 40) = 505, m(2, 38) = 505, m(2, 37) = 505, m(2, 35) = 505, m(2, 29) = 505, m(2, 23) = 505\\&m(1, 67) = 505, m(1, 49) = 505, m(1, 47) = 505, m(1, 41) = 505, m(1, 40) = 505, m(1, 38) = 505, m(1, 37) = 505, m(1, 35) = 505, m(1, 29) = 505, m(1, 23) = 505\\\end{align}

재귀 호출 구조는 트리 형태로 시각화할 수 있으며, 일부 노드(leaf)를 잘라내거나 병렬 컴퓨팅을 활용하여 계산 속도를 높일 수도 있다.

단순히 최대 가치 합뿐만 아니라, 실제로 어떤 물건들이 선택되었는지 알고 싶다면, 계산된

m[i,w]

(또는 `value[i, j]`) 값을 역추적하는 추가적인 재귀 함수를 사용할 수 있다.

```c

/**

최적 해에 포함된 물건들의 인덱스 집합을 반환한다.
i: 고려할 물건의 마지막 인덱스
j: 현재 남은 배낭 용량
/

function find_items(i, j):

if i == 0:

return {} // 빈 집합

// m[i, j]가 m[i-1, j]와 같다는 것은 i번째 물건을 포함하지 않았다는 의미

// (또는 포함해도 가치 변화가 없다는 의미인데, 여기서는 미포함으로 간주해도 무방)

// value 배열을 사용한다고 가정하면, value[i, j]와 value[i-1, j]를 비교

if value[i, j] == value[i-1, j]:

// i번째 물건 미포함, (i-1)번째까지, j 용량에서의 최적 해

return find_items(i-1, j)

else:

// i번째 물건 포함, (i-1)번째까지, (j-w[i]) 용량에서의 최적 해

return {i} ∪ find_items(i-1, j-w[i])

// 최적 해의 물건 집합 찾기 시작

선택된_물건들 := find_items(n, W)

4. 1. 2. 메모이제이션 (Memoization)

0-1 배낭 문제에 대한 동적 프로그래밍 해법은 의사 다항 시간 내에 실행될 수 있다. 물건의 무게

w_1,\,w_2,\,\ldots,\,w_n

와 배낭의 용량

W

가 모두 양의 정수라고 가정하자.

m[i,w]

를 처음

i

개의 물건(물건 1부터

i

까지)을 사용하여 무게 합이

w

를 넘지 않도록 배낭에 담았을 때 얻을 수 있는 최대 가치 합이라고 정의한다.

m[i,w]

는 다음과 같은 재귀적 관계로 정의할 수 있다. '''(정의 A)'''

$m[0,\,w]=0$ (물건이 하나도 없을 때 가치는 0)
만약 $w_i > w\,\!$ 이면 $m[i,\,w]=m[i-1,\,w]$ (물건 $i$ 의 무게가 현재 용량 $w$ 보다 크면 물건 $i$ 를 넣을 수 없으므로, 최대 가치는 물건 $i-1$ 까지 고려했을 때와 같다.)
만약 $w_i \leqslant w$ 이면 $m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_i]+v_i)$ (물건 $i$ 의 무게가 현재 용량 $w$ 보다 작거나 같으면, 물건 $i$ 를 넣지 않는 경우( $m[i-1,\,w]$ )와 물건 $i$ 를 넣는 경우( $m[i-1,w-w_i]+v_i$ ) 중 더 큰 가치를 선택한다.)

이 점화식을 이용하여

m[n,W]

를 계산하면 문제의 해를 얻을 수 있다. 일반적인 동적 프로그래밍 방식은 테이블(배열)을 만들어 이전에 계산된 값을 저장하며 반복적으로 해를 구한다.

하지만 메모이제이션(Memoization) 기법을 사용하면 이 재귀적 정의를 직접 활용하면서 중복 계산을 피할 수 있다. 메모이제이션은 함수의 계산 결과를 저장(메모)해 두었다가 동일한 입력에 대해 함수가 다시 호출될 때 저장된 결과를 반환하여 계산 시간을 단축하는 기법이다. 즉, 재귀 호출 과정에서 이미 계산된

m[i,w]

값이 있다면 다시 계산하지 않고 저장된 값을 사용한다.

다음은 메모이제이션을 사용한 재귀적 해법의 의사 코드이다. `value` 배열은 각 상태 `(i, j)`에 대한 계산 결과를 저장하는 데 사용되며, 초기값 `-1`은 해당 상태가 아직 계산되지 않았음을 나타낸다.

// 입력:

// 가치 (배열 v)

// 무게 (배열 w)

// 물건의 수 (n)

// 배낭 용량 (W)

// (v와 w 배열은 1부터 인덱싱된다고 가정)

// 계산 결과를 저장할 배열 (메모)

Define value[0..n, 0..W]

// 모든 값을 -1로 초기화하여 '계산되지 않음'을 표시

모든 value[i, j]를 -1로 초기화합니다.

// 함수 m(i, j): 물건 1부터 i까지 고려하고, 남은 용량이 j일 때의 최대 가치 계산

m 정의:=(i, j)

{

// 기저 조건: 고려할 물건이 없거나 용량이 없으면 가치는 0

만약 i == 0 또는 j <= 0 이면:

반환 0

// 이미 계산된 값이 있는지 확인 (메모 확인)

만약 (value[i, j] != -1) 이면:

반환 value[i, j] // 저장된 값 반환

// 재귀 계산

결과값 = 0

// 현재 물건(i)의 무게가 용량(j)보다 크면 넣을 수 없음

만약 w[i] > j 이면:

결과값 = m(i-1, j) // 이전 물건까지의 결과와 동일

// 현재 물건(i)을 넣을 수 있는 경우

그렇지 않으면:

// 물건 i를 넣지 않는 경우와 넣는 경우 중 더 큰 가치를 선택

결과값 = max(m(i-1, j), m(i-1, j-w[i]) + v[i])

// 계산된 결과를 저장 (메모)

value[i, j] = 결과값

반환 결과값

}

// 최종 해를 구하기 위해 함수 호출 (모든 물건 n개를 고려, 초기 용량 W)

m(n, W) 실행

이 메모이제이션 방식은 필요한

m[i,w]

값만 계산하게 되므로, 모든

O(nW)

상태를 채우는 반복적 동적 프로그래밍 방식보다 실제 실행 시간이 더 빠를 수 있다. 시간 복잡도는 최악의 경우 모든 상태를 한 번씩 계산하므로

O(nW)

이며, 공간 복잡도는 계산 결과를 저장하기 위한 배열과 재귀 호출 스택의 깊이에 따라 결정되며, 일반적으로

O(nW)

이다.

예를 들어, 10개의 물건이 있고 배낭 용량이 67일 때, 각 물건의 무게(

w

)와 가치(

v

)가 다음과 같다고 하자.

\begin{align}&w[  1]= 23 ,w[  2]= 26,w[  3]= 20,w[  4]= 18,w[  5]= 32,w[  6]= 27,w[  7]= 29,w[  8]= 26,w[  9]= 30,w[ 10]= 27 \\&v[  1]=505 ,v[  2]=352,v[  3]=458,v[  4]=220,v[  5]=354,v[  6]=414,v[  7]=498,v[  8]=545,v[  9]=473,v[ 10]=543 \\\end{align}

위 메모이제이션 방법을 사용하여

m(10,67)

을 계산하면, 재귀 호출 과정에서 다음과 같은 값들이 계산되고 저장된다 (단,

m(i,j) = 0

인 기저 조건 호출은 제외).

\begin{align}&m(10, 67) = 1270\\&m(9, 67) = 1270, m(9, 40) = 678\\&m(8, 67) = 1270, m(8, 40) = 678, m(8, 37) = 545\\&m(7, 67) = 1183, m(7, 41) = 725, m(7, 40) = 678, m(7, 37) = 505\\&m(6, 67) = 1183, m(6, 41) = 725, m(6, 40) = 678, m(6, 38) = 678, m(6, 37) = 505\\&m(5, 67) = 1183, m(5, 41) = 725, m(5, 40) = 678, m(5, 38) = 678, m(5, 37) = 505\\&m(4, 67) = 1183, m(4, 41) = 725, m(4, 40) = 678, m(4, 38) = 678, m(4, 37) = 505, m(4, 35) = 505\\&m(3, 67) = 963, m(3, 49) = 963, m(3, 41) = 505, m(3, 40) = 505, m(3, 38) = 505, m(3, 37) = 505, m(3, 35) = 505, m(3, 23) = 505, m(3, 22) = 458, m(3, 20) = 458\\&m(2, 67) = 857, m(2, 49) = 857, m(2, 47) = 505, m(2, 41) = 505, m(2, 40) = 505, m(2, 38) = 505, m(2, 37) = 505, m(2, 35) = 505, m(2, 29) = 505, m(2, 23) = 505\\&m(1, 67) = 505, m(1, 49) = 505, m(1, 47) = 505, m(1, 41) = 505, m(1, 40) = 505, m(1, 38) = 505, m(1, 37) = 505, m(1, 35) = 505, m(1, 29) = 505, m(1, 23) = 505\\\end{align}

이 계산 과정은 재귀 호출 트리로 시각화될 수 있으며, 메모이제이션은 이 트리에서 동일한 `(i, j)` 상태에 대한 중복 계산을 효과적으로 방지한다.

최대 가치뿐만 아니라 실제로 어떤 물건들이 선택되었는지 알고 싶다면, 계산된

m[i,w]

(또는 `value[i, j]`) 배열을 역추적하여 알아낼 수 있다. 다음은 선택된 물건들의 인덱스 집합을 찾는 함수의 의사 코드이다.

/**

최적 해에 포함된 물건들의 인덱스 집합을 반환한다.
i: 현재 고려 중인 물건의 최대 인덱스
j: 현재 배낭의 남은 용량
m: 메모이제이션 또는 동적 프로그래밍으로 계산된 가치 배열 (value 배열)
w: 물건별 무게 배열
v: 물건별 가치 배열 (역추적 시 필요할 수 있음)
/

function find_selected_items(i: int, j: int): 집합 {

// 기저 조건: 더 이상 고려할 물건이 없다.

만약 i == 0 이면:

반환 {} // 빈 집합

// 물건 i를 넣지 않았을 때의 가치

가치_미포함 = m[i-1, j] // 또는 m(i-1, j) 호출 결과 (메모이제이션 사용 시)

// 물건 i를 넣었을 때의 가치 (넣을 수 있는 경우)

가치_포함 = -∞ // 초기값 (넣을 수 없거나 넣는 것이 손해일 경우 대비)

만약 w[i] <= j 이면:

가치_포함 = m[i-1, j-w[i]] + v[i] // 또는 m(i-1, j-w[i]) + v[i] 호출 결과

// 현재 상태의 최적 가치 m[i, j]가 물건 i를 포함해서 얻어진 것인지 확인

// 주의: m[i, j] == 가치_포함 조건만으로는 부족할 수 있음 (두 선택의 가치가 같을 때)

// 일반적으로 m[i, j] > 가치_미포함 또는 m[i, j] == 가치_포함 조건을 사용

// 원본 소스의 m[i, j] > m[i-1, j]는 물건 i를 포함해야만 가치가 증가하는 경우를 나타냄

만약 m[i, j] != 가치_미포함 이면: // 즉, 물건 i를 포함하는 것이 최적 해의 일부이거나, 포함하지 않는 것과 가치가 같지만 포함하는 선택을 한 경우

// 물건 i를 포함하고, 남은 용량(j-w[i])으로 i-1번째까지의 물건 중 최적 해를 찾는다.

반환 {i} ∪ find_selected_items(i-1, j-w[i])

그렇지 않으면: // 물건 i를 포함하지 않는 것이 최적 해의 일부인 경우

// 물건 i를 포함하지 않고, i-1번째까지의 물건 중 최적 해를 찾는다.

반환 find_selected_items(i-1, j)

}

// 최종적으로 선택된 물건들을 찾기 위해 함수를 호출한다.

find_selected_items(n, W)

Groovy 언어를 사용하여 메모이제이션을 적용한 간결한 코드 예시는 다음과 같다. (`@Memoized` 어노테이션이 메모이제이션 기능을 제공한다. `c`는 무게, `p`는 가치를 나타내는 배열로 가정한다.)

@Memoized // 함수의 결과를 캐싱하여 중복 계산을 방지한다.

int m(int i, int j) { // i: 물건 인덱스 (1부터 시작 가정), j: 현재 용량

// 기저 조건: 고려할 물건이 없으면 가치는 0

if (i == 0) {

return 0

}

// 물건 i를 넣지 않는 경우의 가치 (재귀 호출)

def val_without_i = m(i - 1, j)

// 물건 i를 넣는 경우의 가치 (단, 용량이 충분할 때만 계산)

def val_with_i = 0

if (c[i] <= j) { // c[i]는 물건 i의 무게

val_with_i = m(i - 1, j - c[i]) + p[i] // p[i]는 물건 i의 가치

}

// 두 경우 중 더 큰 가치를 반환

return Math.max(val_without_i, val_with_i)

}

// 최종 해 계산 예시 (물건 1부터 n까지, 초기 용량 W)

// def result = m(n, W)

4. 2. 중간 만남 (Meet-in-the-middle)

0-1 배낭 문제에 대한 또 다른 알고리즘은 1974년에 발견되었으며^[23], 암호학에서 유사하게 명명된 중간 만남 공격과의 유사성 때문에 때로는 '중간 만남(Meet-in-the-middle)'이라고 불린다. 이 알고리즘은 서로 다른 아이템의 수 ''n''에 따라 지수적으로 증가하지만, 최대 허용 무게

W

가 ''n''에 비해 클 경우 동적 계획법 알고리즘보다 선호될 수 있다. 특히, 아이템 무게

w_i

가 음수가 아니지만 정수가 아닌 경우, 동적 계획법 알고리즘은 고정 소수점 산술 등을 사용하여 스케일링 및 반올림을 통해 적용할 수 있다. 그러나 문제의 정확한 답을 얻기 위해 소수점 이하

d

자릿수가 필요한 경우,

W

는

10^d

로 스케일링되어야 하며, 동적 계획법 알고리즘은

O(W10^d)

의 공간과

O(nW10^d)

의 시간을 필요로 한다.
중간 만남 알고리즘은 다음과 같이 작동한다.

입력: 무게와 가치가 있는 아이템들의 집합.
출력: 부분 집합의 가장 큰 결합된 가치.

1. 전체 아이템 집합 {1...''n''}을 대략 같은 크기의 두 집합 ''A''와 ''B''로 분할한다.

2. 각 집합(''A''와 ''B'' 각각)의 모든 부분 집합에 대한 무게와 가치를 계산한다.

3. 각 ''A''의 부분 집합에 대해, 결합된 무게가 ''W''보다 작은 최대 가치를 가지는 ''B''의 부분 집합을 찾는다.

4. 지금까지 찾은 조합 중 가장 큰 결합된 가치를 추적하여 최종 해답으로 반환한다.

이 알고리즘은

O(2^{n/2})

의 공간을 차지한다. 3단계의 효율적인 구현(예: 무게별로 B의 부분 집합을 정렬하고, 더 크거나 같은 가치의 다른 B의 부분 집합보다 더 많이 나가는 B의 부분 집합을 버린 후, 이진 검색을 사용하여 최상의 일치 항목을 찾음)은

O(n2^{n/2})

의 실행 시간을 가진다. 이는 모든

2^n

개의 부분 집합을 검사하는 단순한 무차별 대입 접근 방식의

O(n2^n)

실행 시간보다는 개선된 것이지만, 상수 공간 대신 지수적인 공간을 사용한다는 단점이 있다. ( 베이비 스텝 자이언트 스텝도 참조).

Schroeppel과 Shamir의 부분 집합 합 문제 해결 알고리즘의 통찰력을 사용하여 중간 만남 알고리즘을 개선하려는 연구도 있다. 최첨단 개선 사항 중 하나는 배낭 문제에 대해

O^{*}(2^{n/2})

(다항식 요인까지) 실행 시간을 유지하면서 공간 요구 사항을

O^{*}(2^{0.249999n})

으로 줄이는 무작위 알고리즘이다.^[24] 반대로, 가장 잘 알려진 결정론적 알고리즘은

O^{*}(2^{n/2})

시간에 실행되며

O^{*}(2^{n/4})

의 공간 복잡성을 가진다.^[25]

4. 3. 탐욕 알고리즘 (Greedy Algorithm)

조지 단치히는 무제한 배낭 문제를 해결하기 위해 탐욕 근사 알고리즘을 제안했다.^[27] 그의 방식은 물건들을 무게 단위당 가치가 높은 순서대로 정렬한다(

v_1/w_1\ge\cdots\ge v_n/w_n

). 그런 다음, 가장 가치가 높은 물건부터 배낭에 넣기 시작하여 더 이상 넣을 공간이 없을 때까지 최대한 채운다. 각 물건의 공급이 무제한일 경우, 배낭에 담을 수 있는 물건의 최대 가치를

m

이라고 할 때, 이 탐욕 알고리즘은 최소

m/2

의 가치를 달성할 수 있다.

각 물건의 공급이 제한된 문제의 경우, 위의 알고리즘은 최적이 아닐 수 있다. 그럼에도 불구하고, 간단한 수정을 통해 이 경우를 해결할 수 있다: 모든 물건이 개별적으로 배낭에 들어간다고 가정한다(

w_i \le W

모든

i

에 대해). 가능한 한 탐욕적으로 물건을 채워 해

S_1

을 구성한다. 즉,

S_1=\left\{1,\ldots,k\right\}

여기서

k=\textstyle\max_{1\le k'\le n}\textstyle\sum_{i=1}^{k'} w_i\le W

이다. 또한, 탐욕적으로 채울 때 들어가지 않은 첫 번째 물건(

k+1

번째 물건)만을 포함하는 두 번째 해

S_2=\left\{k+1\right\}

을 구성한다.

S_1\cup S_2

는 문제의 LP 완화에 대한 상한을 제공하므로, 두 해

S_1

과

S_2

중 하나는 최소한

m/2

의 값을 가져야 한다. 따라서

1/2

-근사치를 얻기 위해

S_1

과

S_2

중에서 더 나은 값을 가진 것을 반환한다.

평균 성능은 오차율

n^{-1/2}

에서 분포상 최적 해로 수렴하는 것으로 나타날 수 있다.^[28]

4. 4. 근사 알고리즘 (Approximation Algorithm)

NP-완전 문제의 대부분은 최적의 해를 찾는 것이 매우 어렵기 때문에, 실행 가능한 해를 찾는 것으로 만족해야 하는 경우가 많다. 이때 찾은 해가 최적의 해와 얼마나 가까운지를 보장하는 근사 알고리즘이 유용하게 사용된다.

배낭 문제는 NP-난해 문제이지만, 원하는 만큼 정확한 근사해를 다항 시간 안에 찾을 수 있는 특별한 종류의 문제이다. 이러한 특징을 가진 알고리즘 기법을 완전 다항 시간 근사 기법(FPTAS, Fully Polynomial Time Approximation Scheme)이라고 부른다. 즉, 배낭 문제는 FPTAS를 가지는 대표적인 문제 중 하나이다.

FPTAS는 배낭 문제에서 각 물건의 가치가 정해진 범위 안에 있지 않다는 점을 활용한다. 알고리즘은 먼저 가장 가치가 높은 물건의 가치(

P

)와 전체 물건의 수(

n

), 그리고 사용자가 원하는 정확도(

\varepsilon

)를 이용해 기준값

K = \varepsilon P / n

를 계산한다. 그 다음, 각 물건의 원래 가치(

v_i

)를

K

로 나눈 후 소수점 아래를 버려 새로운 가치(

v'_i = \lfloor v_i / K \rfloor

)를 만든다. 이렇게 하면 가치의 범위가 줄어들어 문제를 더 쉽게 풀 수 있게 된다.

이렇게 조정된 가치(

v'_i

)를 사용하여 동적 계획법과 같은 방법으로 배낭에 넣을 물건들의 조합(

S'

)을 찾는다. 이 방법으로 찾은 해

S'

의 총 가치는 원래 문제의 최적해(

S^*

)의 총 가치의

(1-\varepsilon)

배 이상임이 수학적으로 보장된다 (

\mathrm{profit}(S') \geq (1-\varepsilon) \cdot \mathrm{profit}(S^*)

). 즉, 사용자가

\varepsilon

값을 작게 설정할수록 (예: 0.01) 최적해에 더 가까운 해를 얻을 수 있으며, 이 과정은 입력 크기와

1/\varepsilon

에 대해 다항 시간 안에 완료된다.^[26]

4. 4. 1. 양자 근사 최적화 (Quantum Approximate Optimization)

양자 근사 최적화 알고리즘(QAOA)은 양자 컴퓨터를 사용하여 배낭 문제의 해밀토니안을 최소화하는 방식으로 배낭 문제를 해결하는 데 활용될 수 있다. 배낭 문제의 해밀토니안은 문제의 비용 함수에 제약 조건을 페널티 항으로 포함시켜 구성된다.^[29]

H = -\sum_{i=1}^n v_i x_i + P \left(\sum_{i=1}^n w_i x_i - W\right)^2

여기서

P

는 각 문제 사례에 맞게 미세 조정하여 결정되는 페널티 상수이다.

5. 응용

배낭 문제는 이론적인 개념을 넘어 실생활의 다양한 의사 결정 과정에서 중요한 역할을 한다. 대표적으로 한정된 자원을 여러 대상에 가장 효율적으로 배분하는 자원 할당 문제 해결에 응용될 수 있다. 예를 들어, 투자 및 포트폴리오 선택,^[4] 자산담보부 증권 구성,^[5] 원자재 절약 방안 모색 등이 이에 해당한다. 또한, Merkle–Hellman^[6]과 같은 배낭 암호 시스템의 키 생성 등 암호학 분야나, 제한된 조건에서 최적의 결과를 도출해야 하는 교육 평가(시험 채점 등)^[7] 와 같은 문제 해결에도 배낭 알고리즘이 활용된다.

1999년 스토니브룩 대학교 알고리즘 저장소의 연구에 따르면, 조합 알고리즘 및 알고리즘 엔지니어링 분야와 관련된 75개의 알고리즘 문제 중 배낭 문제는 접미사 트리 및 빈 포장 문제 다음으로 세 번째로 중요한 문제이자, 19번째로 많이 연구되는 문제로 조사되어 그 중요성을 인정받고 있다.^[8]

5. 1. 자원 할당

배낭 문제는 한정된 자원을 여러 대상에 가장 효율적으로 배분하는 방법을 찾는 데 사용될 수 있다. 예를 들어, 제한된 예산 안에서 최대의 수익을 기대할 수 있는 투자 대상을 고르거나 금융 포트폴리오를 구성하는 문제,^[4] 자산담보부 증권 발행 시 어떤 자산을 포함시킬지 결정하는 문제^[5] 등이 대표적인 자원 할당 문제에 해당한다. 이 외에도 원자재 절약 방안 모색이나 Merkle–Hellman^[6]과 같은 배낭 암호 시스템의 키 생성 과정에서도 배낭 문제 해결 방식이 응용된다.

5. 2. 투자 포트폴리오 구성

배낭 문제는 투자자가 제한된 예산 안에서 최대의 수익을 얻을 수 있도록 포트폴리오를 구성하는 데 활용될 수 있다.^[4] 이는 다양한 투자 자산 중에서 어떤 조합을 선택해야 주어진 예산 제약 하에서 가장 높은 기대 수익률을 달성할 수 있는지 결정하는 문제와 유사하다.

5. 3. 암호 시스템

배낭 문제는 Merkle–Hellman^[6] 및 기타 배낭 암호 시스템을 위한 키 생성과 같은 분야에서 활용된다.

5. 4. 시험 문제 출제

배낭 알고리즘은 초기에 시험 문제를 선택하고 채점하는 데 응용되었다. 쉬운 예시를 들면, 각 10점짜리 문제가 12개 출제된 시험에서 응시자가 10문제만 골라 풀어 최대 100점을 얻도록 하는 것은 간단하다. 하지만 문제마다 배점이 다르면 어떤 문제를 선택해야 최고점을 받을 수 있을지 결정하기가 더 복잡해진다.

Feuerman과 Weiss는 문제마다 배점이 다른 총 125점짜리 시험 시스템을 제안했다. 이 시스템에서는 학생들이 일단 모든 문제에 답하도록 한다. 그 후, 배낭 알고리즘을 이용해 학생이 푼 문제들 중에서 총합이 100점에 가장 가까우면서 점수가 가장 높게 나오는 문제 조합을 찾아 최종 점수를 결정한다.^[7]

6. 변형 문제

기본적인 배낭 문제는 매우 광범위하게 응용되기 때문에, 여러 가지 변형된 형태의 문제들이 존재한다. 주요 변형은 다루는 물품의 수, 달성하려는 목표의 수, 혹은 사용 가능한 배낭의 수와 같은 문제의 조건을 변경함으로써 만들어진다.

6. 1. 다차원 배낭 문제 (Multi-dimensional Knapsack Problem)

다차원 배낭 문제는 기본적인 배낭 문제와 달리, 고려해야 할 제약 조건이 무게 하나가 아니라 부피, 면적 등 여러 개(D개)인 경우를 다룬다. 각 물건

i

의 '무게'는 D차원의 벡터

\overline{w_i}=(w_{i1},\ldots,w_{iD})

로 표현되며, 배낭 역시 각 차원별 용량 한계

(W_1,\ldots,W_D)

를 가진다. 목표는 각 차원

d

에서 선택된 물건들의 무게 합이 해당 차원의 용량

W_d

를 넘지 않으면서, 물건들의 총 가치 합을 최대화하는 것이다.

이 문제는 단일 목표(예: 금전적 이익 최대화) 대신 여러 목표를 동시에 고려하는 상황으로 확장될 수도 있다. 예를 들어 경제적 이익뿐만 아니라 환경적 또는 사회적 영향까지 고려하는 경우가 이에 해당한다. 이러한 다중 목표 최적화 문제는 포트폴리오 구성이나 운송 물류 최적화 등에서 자주 등장한다.^[30]^[31]

예를 들어, 크루즈선을 운영하며 코미디언을 고용하는 상황을 생각해보자. 배는 총 승객 무게 제한(예: 1ton)과 개별 연예인 무게 제한(예: 약 453.59kg 미만)이 있을 수 있다. 각 코미디언은 고유한 무게를 가지며, 인기도에 따라 다른 수익을 창출하고, 요구하는 급여도 다르다. 이 경우, 단순히 수익만 극대화하는 것이 아니라, 연예인의 총 인기도를 높이고, 지급할 급여는 최소화하며, 가능한 많은 연예인을 고용하는 등 여러 목표를 동시에 달성하고자 할 수 있다. 이는 여러 제약 조건(무게, 예산 등) 하에서 여러 목표를 최적화해야 하는 다차원, 다중 목표 문제의 예시가 될 수 있다.

계산적인 측면에서 다차원 배낭 문제는 일반 배낭 문제보다 훨씬 풀기 어렵다. 제약 조건의 차원이 2개(

D=2

)만 되어도, P

\ne

NP라는 가정 하에 EPTAS (효율적 다항 시간 근사 해법)를 갖지 않는 것으로 알려져 있다.^[32]

하지만 특정 조건 하에서는 효율적인 해결이 가능하다. '희소 인스턴스'(sparse instance)라고 불리는 문제 유형은 특정 알고리즘^[33]을 통해 효과적으로 풀 수 있다. 다차원 배낭 문제의 인스턴스가 희소하다는 것은, 각 물건

i

에 대해 대부분의 차원(

D-m-1

개,

m)에서 무게값(w_{iy})이 0인 경우를 의미한다. 이러한 희소 인스턴스는 예를 들어, 릴레이 노드가 있는 무선 네트워크에서 패킷 전송을 스케줄링하는 문제 등에서 나타날 수 있다.

^[33] 이 알고리즘은 선택적 다중 변형, 다중 선택 다차원 배낭 문제의 희소 인스턴스 해결에도 적용될 수 있다.^[33]

2차원 배낭 문제(정사각형 공간에 정사각형 물건들을 채우는 문제)의 경우, IHS(Increasing Height Shelf) 알고리즘이 최적 해를 찾는 데 사용될 수 있다. 단, 이는 최적 해에 포함되는 정사각형의 개수가 최대 5개인 경우에 한정된다.^[34]

6. 2. 다중 배낭 문제 (Multiple Knapsacks Problem)

다중 배낭 문제는 여러 개의 배낭이 주어지는 배낭 문제의 한 변형이다. 각 배낭은 저마다 다른 용량 제한을 가지고 있기 때문에, 단순히 하나의 큰 배낭 문제로 취급할 수 없다. 이 문제는 운영 연구 분야에서 물품 적재나 작업 일정 계획과 같은 다양한 실제 문제에 적용될 수 있으며, 다항 시간 근사 알고리즘을 통해 해답에 가까운 값을 효율적으로 찾을 수 있다.^[35]

다중 배낭 문제는 빈 포장 문제와 유사점을 가지지만, 중요한 차이가 있다. 빈 포장 문제는 주어진 모든 물건을 반드시 정해진 통(bin) 안에 모두 넣어야 하는 반면, 다중 배낭 문제에서는 전체 물건 중 일부만 선택하여 배낭에 담을 수 있다는 점에서 다르다.

6. 3. 이차 배낭 문제 (Quadratic Knapsack Problem)

'''이차 배낭 문제'''는 이진 변수와 선형 제약 조건 하에서 이차 목적 함수를 최대화하는 문제이다.^[36] 이 문제에 대한 최초의 언급은 1975년 비츠갈(Witzgall)에 의해 이루어졌으며,^[38] 이후 1980년 갈로(Gallo), 해머(Hammer), 시메오네(Simeone)에 의해 소개되었다.^[37]

6. 4. 온라인 배낭 문제 (Online Knapsack Problem)

'''온라인 배낭 문제'''는 아이템이 하나씩 순서대로 주어지는 상황에서, 각 아이템이 나타날 때마다 즉시 배낭에 넣을지 아니면 버릴지를 결정해야 하는 문제이다. 이 문제에는 두 가지 주요 변형이 있다.

제거 불가 (Irreversible): 한번 배낭에 넣은 아이템은 다시 꺼낼 수 없다.
제거 가능 (Removable): 이미 배낭에 넣은 아이템이라도 나중에 새로운 아이템을 넣기 위해 제거할 수 있다.

한(Han), 카와세(Kawase), 마키노(Makino)는 이 문제에 대한 몇 가지 중요한 결과를 제시했다.^[40]

가중치가 없는 제거 불가 설정에서는 확률적으로 2-경쟁적인 알고리즘을 제안했는데, 이는 이론적으로 가능한 최상의 경쟁 비율이다.
가중치가 있는 제거 가능 설정에서는 2-경쟁적인 알고리즘을 제시했다. 또한, 확률적 알고리즘의 경쟁 비율 하한이 약 1.368임을 증명했고, 어떤 결정적 알고리즘도 상수 경쟁 비율을 가질 수 없음을 보였다.
가중치가 없는 제거 가능 설정에서는 10/7의 경쟁 비율을 가지는 알고리즘을 제시하고, 이 경우 경쟁 비율의 하한이 1.25임을 증명했다.

온라인 배낭 문제에 대해서는 이 외에도 여러 연구가 진행되었다.^[41]^[42]^[43]

참조

_[1] 논문 On the partition of numbers http://plms.oxfordjo[...] 1897-06-25
_[2] 문서 Reducibility Among Combinatorial Problems https://web.archive.[...] Plenum
_[3] 서적 Knapsack problems https://books.google[...] Springer 2022-05-05
_[4] 서적 Knapsack problems https://books.google[...] Springer 2022-05-05
_[5] 서적 Knapsack problems https://books.google[...] Springer 2022-05-05
_[6] 서적 Knapsack problems https://books.google[...] Springer 2022-05-05
_[7] 논문 A Mathematical Programming Model for Test Construction and Scoring 1973-04
_[8] 논문 Who is Interested in Algorithms and Why? Lessons from the Stony Brook Algorithm Repository 1999-09
_[9] 간행물 Where are the hard knapsack problems? http://citeseerx.ist[...] Department of Computer Science, University of Copenhagen, Copenhagen, Denmark 2003
_[10] 논문 Computational Aspects of Hard Knapsack Problems
_[11] 논문 A hybrid algorithm for the unbounded knapsack problem
_[12] 서적 Computer Science – Theory and Applications
_[13] 논문 A lower bound of ½''n''² on linear search programs for the Knapsack problem https://dx.doi.org/1[...]
_[14] 문서
_[15] 논문 Lower bounds for algebraic decision trees https://dx.doi.org/1[...] 1982-03-01
_[16] 논문 Topological Lower Bounds on Algebraic Random Access Machines
_[17] 논문 A Polynomial Linear Search Algorithm for the ''n''-Dimensional Knapsack Problem
_[18] 논문 Unbounded Knapsack Problem : dynamic programming revisited
_[19] 서적 Knapsack Problems: Algorithms and Computer Implementations John Wiley and Sons
_[20] 간행물 Dynamic programming and strong bounds for the 0-1 knapsack problem https://www.jstor.or[...]
_[21] 논문 A hybrid algorithm for the 0-1 knapsack problem
_[22] 논문 A mixture of dynamic programming and branch-and-bound for the subset-sum problem
_[23] 논문 Computing partitions with applications to the knapsack problem
_[24] arXiv Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors 2021-04-12
_[25] 논문 A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems http://epubs.siam.or[...] 1981-08
_[26] 서적 Approximation Algorithms Springer-Verlag Berlin Heidelberg
_[27] 논문 Discrete-Variable Extremum Problems
_[28] 논문 Average-case analysis of a greedy algorithm for the 0/1 knapsack problem 2003-05-01
_[29] 논문 Ising formulations of many NP problems 2014
_[30] 간행물 Heuristics for Cardinality Constrained Portfolio Optimization http://citeseerx.ist[...] The Management School, Imperial College 1998-05
_[31] 문서 Genetic Algorithm Based Bicriterion Optimization for Traction Substations in DC Railway System
_[32] 논문 There is no EPTAS for two dimensional knapsack https://www.cs.techn[...]
_[33] 간행물 Multi-Dimensional OFDMA Scheduling in a Wireless Network with Relay Nodes http://wimnet.ee.col[...]
_[34] 문서 2D knapsack: Packing squares
_[35] 논문 A PTAS for the multiple knapsack problem 2005
_[36] 논문 Global Optimality Conditions and Optimization Methods for Quadratic Knapsack Problems
_[37] 서적 Combinatorial Optimization
_[38] 논문 Mathematical methods of site selection for Electronic Message Systems (EMS) NBS Internal report
_[39] 논문 Approximating Geometric Knapsack via L-packings https://doi.org/10.1[...] 2021
_[40] 논문 Randomized algorithms for online knapsack problems https://www.scienced[...] 2015-01-11
_[41] 논문 Online Unweighted Knapsack Problem with Removal Cost https://link.springe[...] 2014-09-01
_[42] 논문 Online removable knapsack problem under convex function https://www.scienced[...] 2014-06-26
_[43] 간행물 Online Knapsack Problems with a Resource Buffer https://arxiv.org/ab[...] 2024-12-03
_[44] 논문 Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com