0/1 Knapsack 세가지 자료구조

아내에게 한도가 무한대인 카드와, 정해진 무게를 넘어서 담으면 찢어져 버리는 가방을 하나 주었다. 아내는 물건이 종류당 1개씩 있는 가게에 가방을 들고 가서 값어치 있는 물건들을 최대한 많이 가방에 담아서 나오려고 한다. 물건은 당연히 쪼갤 수도 없고, 정해진 용량을 넘을 수 없다. 이것이 바로 0/1 냅색 문제이다.

첫번째 해: top down DP

stack overflow 때문에 일부러 @lru_cache는 쓰지 않고 table을 만들었다.

Item = collections.namedtuple('Item', ('weight', 'value'))


def optimum_subject_to_capacity(items: List[Item], capacity: int) -> int:
    # i: 1:i th items are chooseable
    # w: capacity of a subproblem
    n = len(items)
    table = [[0 for _ in range(1 + capacity)] for _ in range(n + 1)]
    def dp(i, w):
        if i == 0 or w == 0: return 0
        if table[i][w]: return table[i][w]
        weight_ = items[i-1].weight
        value_ = items[i-1].value
        if weight_ <= w:
            table[i][w] = max(dp(i-1, w), dp(i-1, w - weight_) + value_)
        else:
            table[i][w] = dp(i-1, w)
        return table[i][w]
    return dp(n, capacity)

두번째 해: bottom up DP, O(n**2) 공간 

Item = collections.namedtuple('Item', ('weight', 'value'))


def optimum_subject_to_capacity(items: List[Item], capacity: int) -> int:
    # i: 1:i th items are chooseable
    # w: capacity of a subproblem
    n = len(items)
    table = [[0 if c == 0 or r == 0 else None for c in range(1 + capacity)] 
             for r in range(n + 1)]
    for r in range(n + 1):
        for c in range(1 + capacity):
            table[r][c] = table[r-1][c]
            if items[r-1].weight <= c:
                table[r][c] = max(table[r][c],
                                  table[r-1][c - items[r-1].weight] + items[r-1].value
                                  )
    return table(n, capacity)

세번째 해: bottom up DP, O(n) 공간 

Item = collections.namedtuple('Item', ('weight', 'value'))


def optimum_subject_to_capacity(items: List[Item], capacity: int) -> int:
    # i: 1:i th items are chooseable
    # w: capacity of a subproblem
    n = len(items)
    table = [[0 if c == 0 or r == 0 else None for c in range(1 + capacity)] 
             for r in range(n + 1)]
    for r in range(n + 1):
        for c in range(1 + capacity):
            table[r][c] = table[r-1][c]
            if items[r-1].weight <= c:
                table[r][c] = max(table[r][c],
                                  table[r-1][c - items[r-1].weight] + items[r-1].value
                                  )
    return table(n, capacity)

위 세 가지를 서로 변환할 수 있도록 연습 해보았다.