[Algorithm] 0-1 배낭문제(Knapsack Problem) - 백트래킹

🥸 지난 글

이전 글에서 0-1 배낭문제를 다이내믹 프로그래밍으로 푸는 방법을 소개했다. 이번에는 백트래킹으로 풀어보려고 한다.

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

🛤️ Backtracking 백트래킹?

나는 좀 더 간단하게 설명해보고 싶었다. 뭔가 의외로 엄청 어렵게 설명되어 있는 글들이 많았다... Backtracking이라는 단어의 뜻을 살펴보면 추적을 종료한다는 뜻으로도 보인다. 뭘 종료할 건데?? 이를 위해서 우선 Brute-Force(부르트 포스)부터 알아보는 것이 좋을 것 같다.

🦖 Brute-Force 브루트 포스

단어를 해석해보면 난폭한 힘...이라는 뜻으로 해석할 수 있는데, 딱 잘 들어맞는다. 말 그대로 무식하게 푼다는 뜻이다. 위의 배낭 문제를 가장 단순하게 풀어보는 방법은 그냥 모든 경우의 수를 다 넣어보는 것이다.

func knapsack(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> Int {
    var result = 0
    
    func dfs(depth: Int, weight: Int, value: Int) {        
        if weight <= capacity {
            result = max(result, value)
        }
        
        guard depth < weights.count else { return }
                
        dfs(depth: depth + 1, weight: weight + weights[depth], value: value + values[depth])
        dfs(depth: depth + 1, weight: weight, value: value)
    }
    
    dfs(depth: 0, weight: 0, value: 0)
            
    return result
}

나는 dfs를 활용하여 부르트 포스로 배낭문제를 풀어보았다. 단순하다. ABCDE순차적으로 가면서 넣는 경우 안 넣는 경우 모든 경우의 수를 가지 늘리듯이 늘리는 것이다. 그렇게 쭉 간다음에 담은 무게가 배낭의 용량에 들어가면서 가장 높은 값어치를 찾는 방식으로 구현했다.

 

이렇게 구현한다면 ABCDE, 5개의 물건을 넣거나, 안 넣거나의 경우일 것이고 2^5가 되어 32가지 방법만 계산해보면 정답을 알 수 있다. 하지만 이 방법의 ☠️ 단점은 무엇일까? 물건이 하나씩 늘어날 때 마다 계산하는 경우의 수가 두 배씩 늘어난다는 것이다. 예를 들면 10개의 물건이 있다면 1024번 계산을 해야 답을 알 수 있는 것이다. 이전 글에서 보여줬던 DP로 푸는 방법의 경우는 배낭의 무게가 15kg이라면 150번에 끝난다.

🚶 다시 백트래킹

그렇다면 어떻게 해야 계산을 최대한 줄일 수 있을까? 배낭에 물건을 넣는다고 해보자. 배낭에 물건을 넣다가 15kg이 초과했다. 그러면 배낭에 물건을 더 이상 넣을 수 없거니와 그 뒤에 경우의 수는 생각할 필요도 없다.

func knapsack(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> Int {
    var result = 0
    
    func dfs(depth: Int, weight: Int, value: Int) {
              /// 현재 담은 무게는 용량보다 같거나 작아야 한다.
        guard weight <= capacity else { return }
        
        if weight <= capacity {
            result = max(result, value)
        }
        
        guard depth < weights.count else { return }
                
        dfs(depth: depth + 1, weight: weight + weights[depth], value: value + values[depth])
        dfs(depth: depth + 1, weight: weight, value: value)
    }
    
    dfs(depth: 0, weight: 0, value: 0)
            
    return result
}

여기서 한번 더 나아가서 만약에 계산해야 하는 물건을 다 합쳐도 지금 최댓값을 못넘게 된다면 탐색할 필요도 없어진다.

func knapsack(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> Int {
    var result = 0
    
    func dfs(depth: Int, weight: Int, value: Int) {
              /// 현재 담은 무게는 용량보다 같거나 작아야 한다.
        guard weight <= capacity,
              /// 남은 물건의 값과 현재 값을 합치면 최댓값보다 커야 한다.
              value + values[depth...].reduce(0, +) > result else { return }
        
        if weight <= capacity {
            result = max(result, value)
        }
        
        guard depth < weights.count else { return }
                
        dfs(depth: depth + 1, weight: weight + weights[depth], value: value + values[depth])
        dfs(depth: depth + 1, weight: weight, value: value)
    }
    
    dfs(depth: 0, weight: 0, value: 0)
                
    return result
}

이렇게 하면 기존에 32번 계산해야 하는 것을 32번 → 26번 → 12번으로 확 줄일 수가 있다. 이 방법을 백트래킹이라고 한다. 사실 백트래킹은 모든 경우의 수를 계산하기 전에 탈출 조건을 만들어 준다고 생각하면 될 것 같다.

 

부르트 포스로 구현했더라도 어디서 끊어줘야 최대한 계산을 줄일 수 있을지 고민해 보자 ☺️