[Algorithm] 배낭 문제 Knapsack Problem (Swift)

문제 소개 (분할 가능한 배낭 문제)

담을 수 있는 최대 무게가 15kg 인 배낭과 함께 가치가 있는 아이템이 주어졌을 때, 배낭에 어떻게 하면 가장 비싸게 담을 수 있을까?

그리디 알고리즘 (Greedy Algorithm)을 통한 풀이

말이 거창하지 우리는 본능적으로 당연한 정답을 알고 있다. 바로 비싼 것부터 담으면 된다는 것. 이것을 그리디 알고리즘이라고 표현하기도 한다. 지금 이 순간 제일 최적인 답을 선택하는 것이다. 이런 배낭 문제처럼 단순한 문제들은 그렇다. 위의 문제를 그대로 대입하면 변수가 어떻게 주어질 줄 모르겠지만 [12, 1, 4, 1, 2]와 [4, 2, 10, 2, 1]이 주어진다면 10달러짜리 4kg, 4달러짜리 11Kg를 담아주면 된다는 결과가 나온다. 핵심 포인트는 정렬이다. 보통 그리디 알고리즘은 정렬을 하고 접근하게 된다.

import Foundation

func solution(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> [[Int]] {
    var answer: [[Int]] = []
    
    struct Item {
        let value: Int
        let weight: Int
    }
    
    var items: [Item] = []
    
    for i in 0..<weights.count {
        let item = Item(value: values[i], weight: weights[i])
        items.append(item)
    }
    
    items.sort(by: { $0.value > $1.value })
    
    var weight = 0
    
    for item in items {
        if weight + item.weight > capacity {
            answer.append([item.value, capacity-weight])
            break
        } else {
            answer.append([item.value, item.weight])
            weight += item.weight
        }
    }
    
    return answer
}

print(solution(15, [12,1,4,1,2], [4,2,10,1,2])) // [[10, 4], [4, 11]]

 

문제 소개 (0-1 배낭 문제)

아래와 같이 분할이 되지 않는다면...? 무조건 전체 무게를 담아야 한다면? 그리디 알고리즘으로 최적의 값을 찾지 못한다. 가장 최적의 조합을 찾아야 하는 문제이기 때문이다. 15kg 를 다 채우는 것이 이득일 수도 조금 못 채우더라도 조합에 따라 이득이 될 수 있다.

이 문제를 어떻게 풀 수있을까? 세 가지 방법이나 있다! 동적 계획법, 백트래킹, 분기한 정법... 이 있다.

동적 계획법(Dynamic Programming)을 활용한 문제 풀이 및 설명

동적 계획법을 위해서는 계산결과를 저장하고 사용할 table이 필요하다. 코드는 아래와 같다. 이 코드가 뭔 소리여...?라고 할 수 있지만 테이블과 함께 간단하게 설명해 보겠다.

import Foundation

func solution(_ 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 {
            if weights[i-1] > j {
                table[i][j] = table[i-1][j]
            } else {
                table[i][j] = max(table[i-1][j], table[i-1][j-weights[i-1]] + values[i-1])
            }
        }
    }
    
    print(table)
        
    return table[weights.count][capacity]
}

print(solution(15, [12,1,4,1,2], [4,2,10,1,2])) // 15

 

동적 계획법 풀이 설명

table을 출력해 보면 다음과 같다. 이중에 table [5][7]에 있는 14를 분석해 보겠다.

table[5][7]은 A, B, C, D, E를 모두 담을 수 있을 때, 7kg으로 만들 수 있는 최대의 가치이다. 이는 어떻게 판별할 수 있냐면 A, B, C, D를 담는 경우 7kg으로 만들수 있는 최대의 가치(13달러)와 2kg인 E를 무조건 담는다고 생각하는 경우 + A, B, C, D를 담아 5kg으로 만들수 있는 최대의 가치(12달러 + 2달러)를 비교했을 때, 큰 값을 넣어준다. 매번 최선의 선택을 넣어주고 그것을 통해 비교를 해보는 것으로 볼 수 있다.

 

백트래킹(Backtracking)을 활용한 문제 풀이

5개의 물건을 선택하는 경우의 수는 선택하느냐 마느냐 2가지의 경우가 5번 중복되므로 2의 5 제곱인 32가지가 있을 수 있다. 백트래킹은 이런 모든 경우의 수를 전부 고려하는 알고리즘이다. 핵심은 탐색을 할 때, 어떠한 기준으로 탐색할 수 있는 경우의 수를 쳐내느냐 이다. 여기서 다음 노드를 판별할 때, 분할 가능한 배낭 문제의 정답의 결과가 분할 불가능한 배낭 문제의 정답의 결과보다 크거나 같을 수밖에 없는데, 분할 가능한 배낭문제의 정답이 그보다 작게 되면 탐색을 멈추게 한다.

import Foundation

func solution(_ capacity: Int, _ weights: [Int], _ values: [Int]) -> Int {
    struct Item {
        let value: Int
        let weight: Int
    }
    
    var items: [Item] = []
    
    for i in 0..<weights.count {
        let item = Item(value: values[i], weight: weights[i])
        items.append(item)
    }
    
    items.sort(by: { $0.value/$0.weight > $1.value/$1.weight })
    var answer = Array(repeating: 0, count: items.count)
    var maxProfit = 0
    
    func knapsack(_ i: Int, _ w: Int) {
        if i >= items.count || w <= 0 {
            return
        }
        var value = 0
        var weight = 0
        
        for (index, element) in answer.enumerated() {
            value += items[index].value * element
            weight += items[index].weight * element
        }
        
        if items[i].weight <= w {
            let maxValue = greedy(i+1, w-items[i].weight)
            if maxProfit < value + items[i].value + maxValue {
                answer[i] = 1
                maxProfit = max(maxProfit, value+items[i].value)
                knapsack(i+1, w-items[i].weight)
            }
        } else {
            let maxValue = greedy(i+1, w)
            if maxProfit < value + maxValue {
                knapsack(i+1, w)
            }
        }
        
        func greedy(_ i: Int, _ c: Int) -> Int {
            var value = 0
            var total = 0
            
            for j in i..<items.count {
                if total + items[j].weight > c {
                    value += (c-total) * items[j].value/items[j].weight
                    break
                } else {
                    value += items[j].value
                    total += items[j].weight
                }
            }
            
            return value
        }
    }
    
    knapsack(0, capacity)
    
    return maxProfit
}