[Algorithm] 0-1 배낭문제(Knapsack Problem) - DP

알고리즘 하면 나오는 대표 문제인 0-1 배낭문제에 대해서 글을 써보려고 한다.

🎒 0-1 배낭 문제

왜 0-1 배낭 문제일까? 0-1의 의미는 배낭에 넣기, 안 넣기 둘 중 하나만 선택이 되고, 일부만 넣는 것은 불가능하기 때문에 0-1 배낭 문제라는 이름이 붙어졌다.

 

최대 15kg까지 넣을 수 있는 배낭에 다음과 같이 무게와 값어치를 가지고 있는 물건을 넣었을 때 어떻게 담아야 가장 비싸게 담을 수 있을까?

출처: 나무위키

물론 가장 좋은 방법은 물건을 쪼갤 수 있다면 무게당 가장 비싼 걸 1kg씩 차곡차곡 담으면 될 것이다. 하지만 이 문제의 핵심은 물건을 쪼갤 수 없다는 것이다. 그렇다고 무게당 가장 비싼 것부터 담게 된다면 이것이 가장 최적의 방법인지 장담할 수 없다.

🎛️ 동적 계획법(DP)을 사용한 풀이

가장 유명한 풀이인 DP를 활용한 풀이법을 알아보자. 갑자기 뜬금없이 궁금증이 생겼다. 왜 DP는 Dynamic Programming이라는 이름이 붙어졌을까? Dynamic보다는 Static에 가깝고, Programming이라기보다는 Saving같은데...?

 

좀 더 찾아보니 아래와 같은 내용이 있었다. DP라는 이름을 지은 리처드 벨먼의 글을 찾아볼 수 있었다. 좀 요약하자면 1950년대에는 수학연구를 하기 좋은 시기가 아니였는데, 멋진 이름이 필요했다(?) 정도로 해석이 된다.

“An interesting question is, ’Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research....(중략) It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. This, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities”.

Richard Bellman (“Eye of the Hurricane: An autobiography”, World Scientific, 1984)

 

배낭문제로 돌아와서...! DP의 핵심은 작은 문제로 쪼개기 + 재활용이라고 생각한다.

아주 심플하게 위의 그림에서 ABCDE가 붙은것을 활용해 볼 것이다. 아래의 표는 물건이 하나이고, 가방이 1kg부터 15kg일 때 가장 비싸게 담은 경우의 가격을 계산한 표이다. 당연히 물건이 하나니깐 12kg이 넘어가는 순간부터 무조건 담아야 한다. 그러면 $4의 가치의 물건을 가방에 넣을 수 있다.

 

이제 A,B를 담는다면 어떻게 될까? B는 1kg에 $2이니 일단 12kg까지는 무조건 담아야 하고, 12Kg부터는 고민 좀 해봐야 한다.

두 개니까 일단 쉽다. 12kg에는 그대로 $4를 담는 게 이득이고, 13kg부터는 둘 다 담는 게 이득이니 결국 아래와 같이 표가 완성된다.

그러면 이제 A, B, C가 있다고 생각해보자. C는 4킬로니까 어디 보자... 우선 3kg까지는 계산이고 뭐고 무조건 1kg인 B만 담을 수 있다.

이제 3개가 나오니 조금 복잡해진다. 이걸 어떻게 해야할까?

여기서 기존에 계산했던 값을 활용한다. C는 4kg이었기 때문에 기존에 A, B를 사용했을 때, 4kg에서 얻을 수 있는 최대값은 $2이다. A, B를 사용하고 현재 무게 4kg에서 4kg를 뺀 0kg에서의 최댓값 + 4kg의 C를 추가했을 때 최댓 값인 $0 + $10을 비교해서 더 큰 값을 넣는 것이다.

ABC를 4kg에 넣는 방법중 최선의 선택은 $10

 

4kg일 때 ABCD로 최대 담을 수 있는 값어치는 $10이다. 만약에 E가 무조건 들어간다면 4kg에서 2kg을 뺀 ABCD를 2kg에 담는 방법에서 E 2kg을 담게 된다면 $3 + $2로 $5를 담을 수 있는데, ABCD만으로도 $10의 값어치를 담을 수 있기 때문에 그 방법이 제일 이득이다.

ABCDE를 4kg에 넣는 최선의 선택은 $10

결국 정리를 해본다면 아래와 같이 정리가 된다.

let weights = [12, 1, 4, 1, 2] // kg
let values = [4, 2, 10, 1, 2] // $

// 현재 가장 최선의 선택은 바로 위의 줄의 선택과 바로 위의 줄에서 현재 물건을 무조건 넣을 수 있을때 상황과 비교!
table[i][j] = max(table[i-1][j], table[i-1][j-weights[i]] + values[i])

이를 Swift 코드로 옮겨보면 아래와 같다. index의 문제로 아래와 같이 0kg, 0개일 때를 추가해 주었다.

func knapsack(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> Int {
    var table = Array(repeating: Array(repeating: 0, count: capacity + 1), count: weights.count + 1)
    
    for i in 1...weights.count {
        for j in 1...capacity {
            let weight = weights[i - 1]
            let value = values[i - 1]
            
            if j - weight < 0 {
                table[i][j] = table[i - 1][j]
            } else {
                table[i][j] = max(table[i - 1][j], table[i - 1][j - weight] + value)
            }
        }
    }
        
    return table[weights.count][capacity]
}

knapsack(15, [12, 1, 4, 1, 2], [4, 2, 10, 1, 2]) // 정답: 15

// table
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
// [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 4, 4, 4]
// [0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 4, 6, 6, 6]
// [0, 2, 2, 2, 10, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
// [0, 2, 3, 3, 10, 12, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13]
// [0, 2, 3, 4, 10, 12, 13, 14, 15, 15, 15, 15, 15, 15, 15, 15]

 

이렇게 풀게 되면 큰 장점은 우선 시간복잡도가 (배낭의 무게 x 물건의 개수)로 한정된다는 것이다. 또한 테이블을 만들어 놓게 된다면 다른 다양한 경우의 수에서도 바로 답을 도출해 낼 수 있다. 완전 탐색의 경우 (2^아이템 개수)가 되어버린다. (아이템을 넣거나 안 넣거나 2가지 경우가 있으므로)