배낭 문제(Knapsack Problem)의 원리와 구현 - soo:bak
작성일 :
배낭 문제란?
배낭 문제(Knapsack Problem)는 제한된 용량의 배낭에 최대 가치의 물건을 담는 최적화 문제입니다.
배낭의 최대 용량 \(W\)가 주어지고, 각 물건 \(i\)는 무게 \(w_i\)와 가치 \(v_i\)를 가집니다.
목표는 배낭에 담을 수 있는 물건들의 가치 합을 최대화하는 것입니다.
배낭 문제는 동적 계획법(DP)의 대표적인 예시로, 물건 선택 방식에 따라 여러 유형으로 나뉩니다.
배낭 문제의 유형
배낭 문제는 물건을 선택하는 방식에 따라 크게 세 가지로 구분됩니다.
0-1 배낭 문제 (0-1 Knapsack)
각 물건을 한 번만 선택할 수 있습니다.
물건을 넣거나(1) 넣지 않거나(0) 두 가지 선택만 가능합니다.
완전 배낭 문제 (Unbounded Knapsack)
각 물건을 무한히 선택할 수 있습니다.
같은 물건을 여러 번 넣을 수 있습니다.
분할 가능 배낭 문제 (Fractional Knapsack)
물건을 일부만 담을 수 있습니다.
그리디 알고리듬으로 해결할 수 있습니다.
0-1 배낭 문제
가장 기본적인 형태의 배낭 문제입니다.
문제 정의
1
2
3
4
5
6
배낭 용량: W = 7
물건:
물건 1: 무게 1, 가치 1
물건 2: 무게 3, 가치 4
물건 3: 무게 4, 가치 5
물건 4: 무게 5, 가치 7
목표는 무게 합이 7 이하이면서 가치 합이 최대가 되도록 물건을 선택하는 것입니다.
점화식
\(dp[i][w]\)를 “처음 \(i\)개 물건 중에서 무게 합이 \(w\) 이하일 때의 최대 가치”로 정의합니다.
\[dp[i][w] = \max(dp[i-1][w], \; dp[i-1][w-w_i] + v_i)\]- \(dp[i-1][w]\): \(i\)번째 물건을 선택하지 않는 경우
- \(dp[i-1][w-w_i] + v_i\): \(i\)번째 물건을 선택하는 경우 (무게가 충분할 때만)
각 물건에 대해 “선택한다/선택하지 않는다” 두 가지 경우 중 더 큰 가치를 취합니다.
구현 (2차원 DP)
점화식을 그대로 코드로 옮긴 형태입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
int knapsack01(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
// 현재 물건을 선택하지 않는 경우
dp[i][w] = dp[i - 1][w];
// 현재 물건을 선택하는 경우
if (w >= weights[i - 1]) {
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][W];
}
int main() {
int W = 7;
vector<int> weights = {1, 3, 4, 5};
vector<int> values = {1, 4, 5, 7};
cout << "최대 가치: " << knapsack01(W, weights, values) << "\n";
return 0;
}
출력: 최대 가치: 9 (물건 2와 3 선택: 4 + 5 = 9)
공간 최적화 (1차원 DP)
2차원 DP에서 이전 행의 값만 필요하므로 1차원 배열로 최적화할 수 있습니다.
역순으로 순회해야 같은 물건을 여러 번 사용하지 않습니다.
정순으로 순회하면 \(dp[w - w_i]\)가 이미 현재 물건을 포함한 값일 수 있어, 같은 물건을 중복 사용하게 됩니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
int knapsack01Optimized(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
// 역순으로 순회
for (int w = W; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
시간 복잡도: \(O(n \cdot W)\)
공간 복잡도: \(O(W)\)
선택한 물건 추적
어떤 물건을 선택했는지 알아야 할 때는 DP 테이블을 역추적합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
vector<int> getSelectedItems(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// DP 테이블 채우기
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= W; w++) {
dp[i][w] = dp[i - 1][w];
if (w >= weights[i - 1]) {
dp[i][w] = max(dp[i][w],
dp[i - 1][w - weights[i - 1]] + values[i - 1]);
}
}
}
// 역추적
vector<int> selected;
int w = W;
for (int i = n; i > 0 && w > 0; i--) {
if (dp[i][w] != dp[i - 1][w]) {
selected.push_back(i - 1); // 0-indexed
w -= weights[i - 1];
}
}
return selected;
}
\(dp[i][w] \neq dp[i-1][w]\)이면 \(i\)번째 물건이 선택되었음을 의미합니다.
완전 배낭 문제 (Unbounded Knapsack)
각 물건을 무한히 선택할 수 있는 경우입니다.
점화식
\[dp[w] = \max(dp[w], \; dp[w-w_i] + v_i) \quad \text{for all } i\]구현
0-1 배낭과 달리 정순으로 순회합니다.
같은 물건을 여러 번 사용할 수 있으므로, \(dp[w - w_i]\)가 현재 물건을 이미 포함해도 괜찮습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
int unboundedKnapsack(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
// 정순으로 순회
for (int w = weights[i]; w <= W; w++) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
return dp[W];
}
0-1 vs 완전 배낭: 순회 방향의 차이
두 유형의 핵심적인 차이는 1차원 DP에서의 순회 방향입니다.
0-1 배낭은 역순(W에서 0)으로 순회하여 같은 물건의 중복 사용을 방지합니다.
완전 배낭은 정순(0에서 W)으로 순회하여 같은 물건을 여러 번 사용할 수 있게 합니다.
순회 방향만 바꾸면 두 문제를 같은 구조로 해결할 수 있습니다.
분할 가능 배낭 (Fractional Knapsack)
물건을 일부만 담을 수 있는 경우입니다.
이 경우에는 동적 계획법이 아닌 그리디 알고리듬으로 해결합니다.
접근법
- 물건을 가치/무게 비율 기준으로 내림차순 정렬
- 비율이 높은 물건부터 담기
- 배낭이 가득 차면 남은 공간만큼만 물건의 일부를 담기
구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
double fractionalKnapsack(int W, vector<int>& weights, vector<int>& values) {
int n = weights.size();
vector<pair<double, int>> ratio(n); // {비율, 인덱스}
for (int i = 0; i < n; i++) {
ratio[i] = {(double)values[i] / weights[i], i};
}
// 비율 내림차순 정렬
sort(ratio.begin(), ratio.end(), greater<pair<double, int>>());
double totalValue = 0.0;
int remainingW = W;
for (auto [r, i] : ratio) {
if (remainingW >= weights[i]) {
// 전체 담기
totalValue += values[i];
remainingW -= weights[i];
} else {
// 일부만 담기
totalValue += r * remainingW;
break;
}
}
return totalValue;
}
시간 복잡도: \(O(n \log n)\) (정렬)
시간 복잡도
0-1 배낭과 완전 배낭 모두 \(O(n \cdot W)\)의 시간 복잡도를 가집니다.
여기서 \(n\)은 물건의 개수, \(W\)는 배낭의 용량입니다.
이 복잡도는 의사 다항 시간(pseudo-polynomial time)이라고 합니다.
\(W\)가 입력의 크기(비트 수)에 대해 지수적으로 증가할 수 있기 때문입니다.
분할 가능 배낭은 정렬에 \(O(n \log n)\)이 소요됩니다.
실전 예제: 보석 도둑
도둑이 배낭에 보석을 담으려 합니다.
배낭 용량이 주어질 때 담을 수 있는 보석의 최대 가치를 구하는 문제입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, W; // 보석 수, 배낭 용량
cin >> n >> W;
vector<int> weights(n), values(n);
for (int i = 0; i < n; i++) {
cin >> weights[i] >> values[i];
}
vector<int> dp(W + 1, 0);
for (int i = 0; i < n; i++) {
for (int w = W; w >= weights[i]; w--) {
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
}
}
cout << dp[W] << "\n";
return 0;
}
배낭 문제의 변형
배낭 문제의 기본 구조를 활용한 여러 변형이 있습니다.
부분집합 합 (Subset Sum): 주어진 수들 중 일부를 선택하여 특정 합을 만들 수 있는지 판별하는 문제입니다.
동전 교환 (Coin Change): 목표 금액을 만드는 최소 동전 수를 구하는 문제입니다.
목표 합 (Target Sum): 각 수에 +/- 연산을 적용하여 목표 합을 만드는 경우의 수를 구하는 문제입니다.
2차원 배낭: 무게와 부피처럼 두 가지 제약이 있는 경우입니다.
마무리
배낭 문제는 동적 계획법의 핵심 예제로, 다양한 최적화 문제에 응용됩니다.
0-1 배낭은 각 물건을 한 번만 사용할 수 있어 역순 순회가 필요하고, 완전 배낭은 무한 사용이 가능하여 정순 순회를 합니다.
분할 가능 배낭은 그리디 알고리듬으로 해결합니다.
배낭 문제는 자원 할당, 예산 배분, 포트폴리오 최적화 등 실생활의 다양한 문제에 적용됩니다.
관련 글:
관련 문제: