다이나믹 프로그래밍(knapsack problem)

knapsack problem이란

무게 제한이 있는 가방에 value와 weight가 있는 물건을 넣을 때, 넣을 수 있는 최대 value는 몇? 과 같은 문제를 말함.

problem과 sub problem을 잘못 나누면 다음과 같이 된다.

sub problem 에서 problem에 빠진 물건을 항상 넣는 방식으로 나눈게 문제다.

 

각 물건이 없는 경우를 고려하여 문제를 나누면 아래와 같다.

 

이를 2차원의 array에 표현하면서 bottom up 방식으로 풀 수 있다.

 

class ObjectVal:
    def __init__(self, weight : int, value: int) -> None:
        self.weight = weight
        self.value = value

from typing import List

class KnapSack:
    def __init__(self, objects : List[ObjectVal]) -> None:
        self._objects = objects
    
    def _InitDPTable(self, objectCnt : int, weightLimit : int):
        self._dp = [[None for i in range(weightLimit + 1)] for j in range(objectCnt + 1)]
        for rowIdx in range(objectCnt + 1):
            self._dp[rowIdx][0] = 0

        for colIdx in range(weightLimit + 1):
            self._dp[0][colIdx] = 0
    
    def TopDown(self, weightLimit : int) -> int:
        objectEndIdx = len(self._objects)
        self._InitDPTable(objectEndIdx, weightLimit)
        return self._RecurTopDown(objectEndIdx, weightLimit)
    
    def _RecurTopDown(self, objectIdx : int, weightLimit : int) -> int:
        if objectIdx < 0 or weightLimit < 0:
            return 0
        dpVal = self._dp[objectIdx][weightLimit]
        if dpVal is None:
            prevObjectIdx = objectIdx - 1
            notTakingValue = self._RecurTopDown(prevObjectIdx, weightLimit)

            curObjectWeight = self._objects[objectIdx - 1].weight
            curObjectValue = self._objects[objectIdx - 1].value
            takingValue = self._RecurTopDown(prevObjectIdx, weightLimit - curObjectWeight) + curObjectValue

            maxValue = max(notTakingValue, takingValue)
            self._dp[objectIdx][weightLimit] = maxValue
            return maxValue
        return dpVal
    
    def BottomUp(self, weightLimit : int) -> int:
        objectEndIdx = len(self._objects)
        self._InitDPTable(objectEndIdx, weightLimit)

        for rowIdx in range(1, objectEndIdx + 1):
            for colIdx in range(1, weightLimit + 1):
                prevObjIdx = rowIdx - 1
                notTakingValue = self._dp[prevObjIdx][colIdx]

                weight = self._objects[rowIdx - 1].weight
                value = self._objects[rowIdx - 1].value
                takingValue = 0
                prev_weight_limit = colIdx - weight
                if prev_weight_limit < 0:
                    takingValue = 0
                else:
                    takingValue = self._dp[prevObjIdx][prev_weight_limit] + value
                
                maxValue = max(notTakingValue, takingValue)
                self._dp[rowIdx][colIdx] = maxValue

        return self._dp[objectEndIdx][weightLimit]


objects = [ObjectVal(1,30),ObjectVal(2,20),ObjectVal(3,40),ObjectVal(4,10)]
knapSack = KnapSack(objects)
print(knapSack.TopDown(5))
print(knapSack.BottomUp(5))

 

출처 : (5) 코딩테스트, 중급, knapsack problem - YouTube