[이론] 배낭 문제

 🤔 배낭 문제란?

담을 수 있는 최대 용량이 정해진 배낭과 각 물건의 무게와 가치가 주어졌을 때, 배낭에 담은 물건들의 가치의 합이 최대가 되면서 배낭의 최대 용량을 초과하지 않도록 물건을 선택하는 문제를 말한다.

 

'배낭'에 담을 수 있는 최대 용량이 정해져 있기 때문에 무게 대비 가치를 고려하는 것이 중요하다.

---

 🎒 종류

배낭 문제는 분할 가능 여부에 따라 두 종류로 나누어 볼 수 있다.

  1. Fractional Knapsack (분할 가능한 배낭)

• 물건을 분할해서 담을 수 있는 경우이다.
• 단위 무게당 가치가 높은 순으로 가방에 채워 넣는다. 그리디 알고리즘을 사용하면 풀 수 있다.
  

 

  2. 0–1 Knapsack (분할 불가능한 배낭)

• 물건을 통째로 넣거나 아예 넣지 않는 경우만 존재한다. (넣지 않으면 0, 넣으면 1)
• 부분집합 선택 문제로, 조합의 수가 많아지고 그리디 알고리즘만으로는 최적해를 구할 수 없다. 따라서 동적 계획법(DP), 백트래킹 등의 조합 최적화 문제의 풀이 방법이 필요하다.
  

 

이외에도 동일한 물건을 여러 개 담을 수 있는 Unbounded Knapsack, 카테고리별로 하나만 고를 수 있는 Multiple Choice Knapsack 등이 있다.

(사진 출처: 나무위키)

---

 📌 풀이 방법

  1. Fractional Knapsack (분할 가능한 배낭)

• 먼저 물건들의 무게당 가치를 구한 후, 값을 내림차순으로 정렬하여 최대 용량에 도달할 때까지 더해준다.

  2. 0–1 Knapsack (분할 불가능한 배낭)

• 동적 프로그래밍(DP)를 활용하여 해결한다. 풀이 방법은 다음과 같다.
• 먼저, n개의 물건, 최대 용량 w가 있다고 하자.dp[i][j]는 i번째 물건까지 고려했을 때 무게 j로 담을 수 있는 최대 가치로 정의한다. weight[i]는 i번째 물건의 무게, value[i]는 i번째 물건의 가치를 의미한다. 점화식은 다음과 같다.

if weight[i] ≤ j:
	dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
    // i번째 물건의 무게가 배낭의 (임시)최대 용량 j를 넘지 않는 경우, 이전 값과 추가한 값 중 더 큰 가치를 저장한다.
    // j-weght[i]: 배낭에 물건 i(무게가 weight[i]인)를 담을 공간을 마련.
    
else: 
	dp[i][j] = dp[i-1][j] // 최대 용량을 넘는 경우, 넣지 못하므로 이전과 같은 값이다.

• 위 점화식을 바탕으로 의사코드를 작성해보자.

for i=0 to n:
    	dp[i][0] = 0 // 배낭의 최대 용량이 0일 때.
    for j=0 to w:
    	dp[0][j] = 0 // 0번째 물건. 즉, 어떤 물건도 고려하지 않는 경우.
    for i=1 to n: // 첫번째 물건부터 n번째 물건까지.
    	for j=1 to w: // 최대 용량이 1일 때부터 w일 때까지. 즉, j는 배낭의 임시 용량을 의미한다.
        	if(weight[i] > j):
            	dp[i][j] = dp[i-1][j]
            else:
            	dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])

• 시간 복잡도와 공간 복잡도 모두 O(n-w)이지만, 1차원 배열로 O(w)까지 최적화할 수 있다.

---

 🌀 NP-완전성과 의의

0-1 Knapscak은 NP-완전 문제에 속한다. 다시 말해, 가장 효율적인(빠른) 방법으로는 일반적인 해법이 알려져 있지 않다는 것이다.
물건이 많아지고, 배낭의 무게 제한이 커질수록 가능한 조합이 기하급수적으로 증가하고, 모든 경우를 다 고려하는 브루트포스 방식은 너무 오래 걸리기 때문이다.

 

그래서 우리는 시간 효율성을 위해 동적 계획법(DP)이나 근사 알고리즘, 그리티 알고리즘을 활용하여 최적해, 또는 그에 가까운 값을 빠르게 구하려는 노력을 한다. 하지만, 분할 가능한 경우에는 단순 정렬 및 그리디 알고리즘으로 다항 시간 내에 해결할 수 있다.

---

 ✍🏻 관련 문제

 🤔 문제

백준 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865
백준 16493번: 최대 페이지 수 https://www.acmicpc.net/problem/16493

 

💡문제풀이

[BOJ C++] 백준 12865번: 평범한 배낭
[BOJ C++] 백준 16493번: 최대 페이지 수