[알고리즘] 배낭 문제 (0-1 Knapsack Problem)

 

배낭 문제(0-1 Knapscak Problem)는 N개의 물건과 배낭의 용량이 주어질 때 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 각 물건은 1개씩만 있고 물건마다 무게와 가치가 주어진다.

 

문제 조건

W = 배낭의 용량

vᵢ = i번째 물건의 가치

wᵢ = i번째 물건의 무게

K[i, w] = 1번 물건부터 i번째 물건까지만 고려하고, 배낭 용량이 w일 때의 최대 가치 (i = 1 ~ n, w = 1 ~ W)

 

이때 K[i, w]를 재귀적으로 표현하면

 

1. ( i = 0 or w = 0 )  🡢  0

i가 0이거나 w가 0이면 0이다.

 

2. ( wᵢ > w )  🡢  K[i - 1, w]

i번째 물건의 무게 wᵢ가 남은 배낭 용량보다 크면 i번째 물건을 포함하지 못한다.

 

3. ( i > 0 and wᵢ <= w )  🡢  max(vᵢ + K[i - 1, w - wᵢ], K[i - 1, w])

i가 0보다 크고 i번째 물건의 무게 wᵢ가 남은 배낭 용량보다 작거나 같으면 i번째 물건을 포함한 상태의 최대가치와 포함하지 않았을 때의 최대가치를 비교해서 더 큰 경우를 선택한다.

 

위를 pseudocode로 표현

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ᵢ > w
        	K[i, w] = K[[i - 1, w]
        ELSE
        	K[i, w] = max(vᵢ + K[i - 1, w - wᵢ], K[i - 1, w])
 
 RETURN K[n, W]

 

 

문제 적용 예시)

문제 조건

배낭의 용량 : W = 10kg

1번째 물건 : 5kg / 10만원

2번째 물건 : 4kg / 40만원

3번째 물건 : 6kg / 30만원

4번째 물건 : 3kg / 50만원

 

i	고려 물건들		w=0	w=1	w=2	w=3	w=4	w=5	w=6	w=7	w=8	w=9	w=10
0	{}		0	0	0	0	0	0	0	0	0	0	0
1	{1}		0	0	0	0	0	10	10	10	10	10	10
2	{1, 2}		0	0	0	0	40	40	40	40	40	50	50
3	{1, 2, 3}		0	0	0	0	40	40	40	40	40	50	70
4	{1, 2, 3, 4}		0	0	0	50	50	50	50	90	90	90	90

 

배열의 0번 행과 0번 열의 원소를 0으로 초기화한다.

물건 1을 고려해서 w를 늘려가면서 배낭에 담아본다.

앞에 구한 최적해와 물건 2를 고려해서 배낭에 담아본다.

앞에 구한 최적해와 물건 3을 고려해서 배낭에 담아본다.

앞에 구한 최적해와 물건 4를 고려해서 배낭에 담아본다.

K[4, 10] 위치에 저장된 값이 최대 가치이다.