[알고리즘] 동적 계획법(Dynamic Programming): 0/1 Knapsack

 0. 0/1 Knapsack

배낭에 물건을 쪼개지 않고 담는 문제를 0/1 Knapsack이라고 한다.

이 문제를 부분집합으로 풀게 되면 시간 복잡도가 O(2^n)이므로, DP로 접근하는 것이 효율적인 문제가 된다.

---

1. 0/1 Knapsack 정의

W = 배낭의 용량

(v_i, w_i) = (물건의 가치, 물건의 무게)

K[i, w] = 물건 i까지 고려했을 때, 배낭의 용량이 w일 때의 최대 가치

 

1-1. K[i, w] 수식 정의

1-2. i번째 물건을 고려할 때

1-3. 의사 코드

배낭의 용량 W
n개의 물건과 각 물건 i의 무게 w_i와 가치 v_i, (단, i = 1, 2, ..., n)
K[n, W]

For i in 0 -> n : K[i, 0] <- 0
For w in 0 -> W : K[0, w] <- 0

For i in 1 -> n
	For w in 1 -> W
    	If w_i > w
        	K[i, w] <- K[i - 1, w]
        Else
        	K[i, w] <- max(v_i + K[i - 1, w - w_i], K[i - 1, w])

---

2. 코드

아래 이미지를 참고하여 코드를 작성하였다.

2-1. 기본 코드

2-2. 개선된 코드

2-3. 물건의 개수가 무제한 일때의 코드