[Algorithm] 0/1 배낭 문제(Knapsack) 알아보기

개요

알고리즘 학습을 하다 보면 반드시 한 번쯤은 마주치게 되는 유명한 문제가 있습니다. 바로 '배낭 채우기 문제' (Knapsack Problem)입니다.

 

배낭 문제는 크게 두 가지로 나뉩니다. 물건을 부분적으로 쪼갤 수 있는 Fractional Knapsack 문제와, 물건을 온전히 하나만 선택하거나 선택하지 않아야 하는 0/1 Knapsack 문제가 있습니다.

 

실제 현실 세계에서는 물건을 마음대로 쪼개서 담을 수 없는 경우가 대부분이기 때문에, 0/1 배낭 문제가 주로 사용되고는 합니다.

 

본 글에서는 두 가지 문제 중  0/1 Knapsack 문제에 대해서 정리하고자 합니다.

 

배낭 문제 해결을 위한 초기 접근 방법들

도둑이 보석 가게에 침입했다.

배낭의 최대 용량을 초과하면 찢어지기 때문에, 무게 제한 안에서 가장 비싼 보석들을 선택해야 한다. 어떻게 담아야 이익을 극대화할 수 있을까?

 

배낭 문제 (knapsack)은 위와 같은 상황에서 최대한 많은 이익을 가져갈 수 있는 물건을 선택하는 문제입니다.

---

일반적으로 사람이 생각하기에는 무게제한을 생각하여 최대한 많은 이익을 가져가는 물건을 선택하기에는 어렵지 않습니다.

 

문제는 코드로 구현을 할 때인데 먼저 생각나는 알고리즘은 Greedy 알고리즘과 모든 가능한 경우를 넣어보는 Brute-Force 알고리즘이 생각이 납니다.

 

결론부터 말하자면, 이 두 알고리즘은 사용하기에 적합하지 않습니다.

1. Brute-Force Algorithm

모든 가능한 조합을 시도해보는 완전 탐색 방식입니다. n개의 물건이 있다면, 각 물건마다 선택하거나 선택하지 않는 두 가지 경우가 있으므로 총 2^n개의 조합이 발생합니다.

 

예를 들어 물건이 3개라면:

• 아무것도 선택하지 않는 경우: {}
• 한 개만 선택하는 경우: {1}, {2}, {3}
• 두 개를 선택하는 경우: {1,2}, {1,3}, {2,3}
• 세 개 모두 선택하는 경우: {1,2,3}

이렇게 총 8(2^3)가지 경우가 발생합니다. 물건의 개수가 증가할수록 경우의 수는 기하급수적으로 증가하여, 시간 복잡도는 O(2^n)이 됩니다. 따라서 물건의 개수가 많아지면 현실적으로 해결이 불가능해집니다.

 

 

[Algorithm] 완전 탐색, 브루트 포스: 가장 단순한 알고리즘(Brute Force) 알아보기

 

2. Greedy Algorithm

탐욕 알고리즘은 매 선택에서 가장 좋아 보이는 것을 고르는 방식입니다. 0/1 배낭 문제에서 그리디 알고리즘을 적용한다면 다음과 같은 방법들을 생각해볼 수 있습니다:

1. 가치가 가장 높은 물건부터 선택
2. 무게가 가장 가벼운 물건부터 선택
3. 무게당 가치(가치/무게)가 가장 높은 물건부터 선택

하지만 이 방법들은 최적해를 보장하지 못합니다. 다음 예시를 봅시다:

물건 1: 가치 = 100, 무게 = 50
물건 2: 가치 = 60, 무게 = 20
물건 3: 가치 = 80, 무게 = 30
배낭 용량 = 50

 

• 그리디 알고리즘에서는 가치가 높은 물건부터 선택합니다.
• 먼저 물건 1을 선택합니다. (용량 50 사용, 배낭 용량 50 모두 소진)

이렇게 되면 물건 1만 선택하고 종료되며, 총 가치 = 100입니다.

 

그러나 실제 최적해는 물건 2와 물건 3을 선택하는 것입니다.

• 물건 2 (가치 60, 무게 20)와 물건 3 (가치 80, 무게 30)을 선택하면, 총 무게는 50이고, 총 가치 = 60 + 80 = 140으로 더 높은 가치를 얻을 수 있습니다.

따라서 가치가 높은 물건을 우선 선택하는 방식은 최적해를 보장하지 않으며, 물건 2와 물건 3을 선택하는 것이 더 높은 가치를 얻을 수 있는 해입니다.

 

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기

 

0/1 Knapsack 알고리즘 해결 방법 : DP

위에서 알 수 있듯이 브루트 포스 알고리즘은 시간초과가 발생할 가능성이 높고 그리디 알고리즘은 최적해를 보장하지 않습니다.

 

따라서 이러한 문제를 해결하기 위해 우리는 동적 프로그래밍(Dynamic Programming) 방식을 사용합니다.

 

동적 프로그래밍은 문제를 작은 하위 문제들로 나누고, 각 하위 문제의 결과를 저장하여 재사용함으로써 중복 계산을 피하는 방식입니다.

 

[Algorithm] 동적 계획법(Dynamic Programming, DP, Java) 알아보기

자세한 내용은 위 포스팅에서 확인 가능합니다.

---

DP를 사용한 해결과정

0/1 배낭 문제를 DP로 해결하는 방법을 살펴보겠습니다:

 

1. 2차원 배열 생성

 

• dp[i][w]
  • i번째 물건까지 고려했을 때, 무게 w에서 얻을 수 있는 최대 가치
• i
  • 현재까지 고려한 물건의 개수 (0 ~ n)
• w
  • 현재 가방의 무게 (0 ~ W)

 

2. 점화식 도출

dp[i][w] = Math.max(dp[i-1][w],                       // 선택하지 않는 경우
                    dp[i-1][w-weights[i-1]] + values[i-1])  // 선택하는 경우

• 현재 물건을 선택할 수 있는 경우 (weights[i-1] ≤ w)
  • 현재 물건을 넣을 수 있는 경우는 물건의 무게가 배낭의 현재 용량(w)보다 작거나 같은 경우입니다.
• 이때는 두 가지 선택지 중 더 나은 것(최대의 가치)을 선택합니다:
  1. 현재 물건을 선택하지 않는 경우: dp[i-1][w]
  2. 현재 물건을 선택하는 경우: dp[i-1][w-weights[i-1]] + values[i-1]
     • 현재 물건을 선택할 경우, 배낭의 용량에서 현재 물건의 무게만큼 차감하고 (w-weights[i-1]), 현재 물건의 가치를 더해줍니다 (+ values[i-1]).
• 물건을 선택할 수 없는 경우 (weights[i-1] > w)
  • 현재 물건의 무게가 배낭의 현재 용량보다 큰 경우입니다.
  • 이때는 이전 상태의 가치를 그대로 가져옵니다: dp[i-1][w]

3. 코드로 녹여내기

// DP 테이블 생성
int[][] dp = new int[n + 1][capacity + 1];

// DP 테이블 채우기
for (int i = 1; i <= n; i++) {
    for (int w = 0; w <= capacity; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = Math.max(dp[i-1][w], 
                               dp[i-1][w-weights[i-1]] + values[i-1]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

 

0/1 Knapsack 알고리즘 대표 문제

0/1 knapsack 알고리즘을 사용한 대표적인 문제는 "백준 - 평범한 배낭" 문제입니다.

 

https://www.acmicpc.net/problem/12865

---

[백준, 12865번] 평범한 배낭 (다이나믹 프로그래밍 : DP, 배낭 문제 : Knapsack, Java)

 

위 포스팅에서 자세한 설명을 확인할 수 있습니다.