#Knapsack Problem

학부생 때 제대로 이해 못했던 알고리즘을 지금에서야 공부하고 있다. 무엇보다 기본이 가장 중요하니까-

알고리즘은 간단하지만, 확인하는 절차가 상당히 오래 걸렸다.

배낭 문제의 목적은 

n개의 무게와 가격을 가진 각각의 아이템 중에서,

배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 아이템의 부분집합을 구하는 것

이다.

대략적인 설명과 알고리즘은 'Youtube 권오흠님의 알고리즘-동적계획법 영상'의 슬라이드로 대체한다. 설명이 조금 부족해 보일 수도 있지만, 동적 계획법을 잘만 이해하고 있다면 어렵지 않게 이해할 수 있을 것이라고 본다.

알고리즘이 정말 너무 간단하다....

알고리즘의 핵심은 결국 'M'이라는 배열에 memoization 작업을 하는 것이다.

아래는 내가 직접 만들어서 푼 문제이다.

def knapsack():
   wi = [13, 5, 8, 12]
   p = [250, 120, 170, 50]
   n = len(wi)
   W = 25
   m = [[0 for col in range(W+1)] for row in range(n+1)]

   for i in range(0, W+1) : m[0][i] = 0

   for i in range(1, n+1) :
      for j in range(1, W+1) :
         if j>W : m[i][j] = m[i-1][W]
         else :
            if j-wi[i-1] < 0: m[i][j] = m[i-1][j]
            else : m[i][j] = max(m[i-1][j], p[i-1] + m[i-1][j-wi[i-1]])

   return m[n][W]

검산을 위해 직접 표를 그려봤다.

행은 아이템을, 최대 무게를 나타내는 것이다. 0의 인덱스를 가진 행은 memoization을 위한 사전 작업이라고 보면 된다.

(색깔은 검산 쉽게 하려고 색칠한 거라 신경 안 써도 된다.)