[python] KnapSack 0-1 이걸로 스트레스 받는거 멈춰!

Sanghoon Han·2021년 4월 18일

글을 쓰게 된 이유

코테 문제를 풀다보면 Knapsack 문제가 자주나온다.

자주 나올때마다 아 이거 저번에 풀었던거지~ ㅎㅎ
음.. 어떻게 했었지
아............;;;;;;;

이제 이런 상황 멈춰!!!!

knapsack 으로 문제를 왜 해결해야 할까?

철수는 백패킹을 가려한다.
백패킹을 가기위해 20L 백팩을 준비했다.
다음은 철수의 물건과 각 물건으로 얻을수 있는 철수의 행복도 이다
[아이패드, 참치캔, 맥주] , [10L ,5L, 9L] , [5, 10, 8]

각 물건마다 넣을지 안넣을지 모든 경우의 수를 보게 되면
2 x 2 x2 = 8가지 이다.
8가지 중 20L를 넘지 않고 행복도를 최대로 하는것을 찾으면 된다.
만약 철수의 물건이 10개라면? 100개라면? 1000개라면????
2 x 2 x 2 x......... = 2 ^(n) 이다.
즉 시간 복잡도가 O(2^n) 이다. 이는 지금의 컴퓨터 기술론 해결할 수 없다.

일단 2^n 이게 코드를 작성해보자.


weights =[0] + [10, 5, 9] #0을 넣어줌으로써 코드가 깔끔하게 작성됨
values = [0] + [5, 10, 8]
CAPACITY = 20

def knapsack(n:int,C:int) -> int:
  if n == 0 or C == 0:
     #아이템 목록을 다 봤꺼나 이미 Capacity가 0일때.
     result = 0
  elif weights[n] > C:
     #지금의 Capacity로는 n번째 아이템의 물건을 넣을수 없다면
     result = knapsack(n-1, C)
  else:
     #물건을 넣지 않을때
     value_without_this_item = knapsack(n-1, C)
     #물건을 넣을때
     value_with_this_item = values[n] + knapsack(n-1, C-weights[n])
     #두개의 상황비교해서 큰값을 결과로 저장
     result = max(value_without_this_item, value_with_this_item)
  return result
knapsack(3, CAPACITY)

Memoization

이걸 개선 하려면 어떻게 해야할까?
만약 knapsack 에서 각 n과 C에 계산된 결과를 저장해 놓으면
재귀가 돌때 또 가지를 치기 보단 저장된 값을 불러오면 된다

즉 arr[n][C]에 값들을 저장해 놓으면 되겠구나
위 코들를 수정해보자


weights =[0] + [10, 5, 9] #0을 넣어줌으로써 코드가 깔끔하게 작성됨
values = [0] + [5, 10, 8]
CAPACITY = 20

"""
추가한 부분 : 재귀를 돌때 값을 저장해줄 empty array를 만들어 주었다.
값은 -1로 채워주었다. -1이 아니라면 재귀를 돌고 값이 저장된 것이다.
"""
arr = [[-1] * (CAPACITY + 1) for _ in range(len(weights))]

def knapsack(n:int,C:int) -> int:

  """
  추가한 부분 : 만약 n번째 아이템상황과 그때의 Capacity에서 최댓값이 저장되어 있다면
  재귀를 돌지않고 저장된 값으로 return해준다. -1로 초기화를 해주었기에 -1과 비교해준다.
  """
  if arr[n][C] != -1:
     return arr[n][C]
  if n == 0 or C == 0:
     #아이템 목록을 다 봤꺼나 이미 Capacity가 0일때.
     result = 0
  elif weights[n] > C:
     #지금의 Capacity로는 n번째 아이템의 물건을 넣을수 없다면
     result = knapsack(n-1, C)
  else:
     #물건을 넣지 않을때
     value_without_this_item = knapsack(n-1, C)
     #물건을 넣을때
     value_with_this_item = values[n] + knapsack(n-1, C-weights[n])
     #두개의 상황비교해서 큰값을 결과로 저장
     result = max(value_without_this_item, value_with_this_item)
  """
  추가한 부분 : 만약 result값이 재귀를 돌고 나왔다면 이 값을 만들때의 n과 C를 
  arr[n][C]에 저장해준다.
  """
  arr[n][C] = result
  return result
  
knapsack(3, CAPACITY)

Bonus Bottom-up 방법


def knapsack(n:int, C:int) -> int:
  arr = [[-1]*(C+1) for _ in range(n+1)]]
  for n_ in range(n+1):
      for c_ in range(C+1):
         #만약 넣을수 있는 아이템이 없거나, 넣을수 있는 용량이 0이라면
         if n_ == 0 or c_ == 0:
             arr[n_][c_] = 0
         #만약 넣을수 있는 아이템의 무게가 넣을수 있는 용량보다 크다면
         elif w[n_] > c_ : 
            arr[n_][c_] = arr[n_-1][c_] 
         #물건을 넣을수 있다면
         else:
            arr[n_][c_] = max(v[n_] + arr[n_-1][c_-w[n_]], #이전 상황에서 물건을 추가해줬을때와
                              arr[n_-1][c_]) #이전 상황에서 capacity가 그대로 일때와 비교해서 큰값을 저장해준다.
         
  return arr[n][C]