[알고리즘] 배낭 알고리즘(Knapsack algorithm) 기본 개념과 구현 방법

배낭 알고리즘(Knapsack algorithm)

 

알고리즘에서 DP를 배울때 등장하는 유명한 문제가 있습니다. 제목과 같이 바로 배낭알고리즘이지요. 배낭알고리즘도 여러가지가 있지만, 우리는 조건이 가장 간단한 0/1 배낭 알고리즘 문제를 알아보도록 하겠습니다.

 

상황은 이렇습니다.

어떤 REAKWON이라는 이름의 도둑놈이 있습니다. 이 도둑은 새벽 늦은 시간 도둑질을 하기 위해서 남의 집에 들어가는데 까지는 성공했습니다. 그리고 훔쳐갈 물건들을 담기 위해 배낭도 챙겼지요. 데헷

하지만 이 도둑은 안타깝게도 아이큐가 70입니다. 배낭의 용량은 한정되어 있고 무거우면 들고갈 수도 없으므로 가장 값어치가 비싸고, 무게가 적은 물건들을 최대한 많이 담아가야합니다.

하지만 조건이 있습니다.

1) 물건을 부분적으로 담을 수는 없습니다.

2) 물건들은 모두 한개씩만 있습니다. 예를 들어 똑같은 반지가 2개일 수 없다는 이야기입니다.

 

도둑은 현재 15의 무게를 담을 수 있는 배낭을 가지고 있습니다. 그리고 아래와 같이 그 집의 물건이 있지요. 

 

items	weight	value
[0]	5	8
[1]	8	11
[2]	3	3
[3]	4	6
[4]	2	4

 

 

이 상황에서 도둑이 훔쳐갈 수 있는 최대의 값을 구하는 것입니다.

 

어떻게 도둑을 도와줄것인가?

아 그냥 무게가 가장 적은거 순서대로 훔쳐가면 되지 않을까요?

라고 생각하신다면 다시 한번 생각해봅시다.

위의 물건들을 가장 작은 무게가 나가는 것을 훔쳐가게 된다면 items[4], items[2], items[3], items[0]만 가져갈 수 있고, 총 가치는 21이 되고 총 용량은 14가 됩니다.

하지만 items[0], items[1], items[4]를 선택한다면 총 가치는 23이 되고, 용량은 15로 더 비싼물건을 훔칠 수 있습니다.

 

그렇기 때문에 무게가 덜 나가는 순으로 정렬해서 문제를 해결할 수가 없는것이죠.

그래서 단순 무식하게 한번 접근해봅시다.

도둑은 그 물건을 훔쳐갈 수 있느냐, 훔쳐갈 수 없느냐 이 둘만 고려합니다. 

 

1) 훔쳐갈때 

만약 어떤 물건을 훔쳐갈 수 있다고 한다면 현재 무게가 그 물건의 무게만큼 무거워지요. 하지만 배낭 용량을 초과할 수는 없습니다. 그럴땐 그 물건을 배낭에 담을 수가 없습니다.

현재 그 물건들을 배열로 표현(items)하고, 어떤 물건을 고려 할때 그 아이템의 인덱스를 pos라고 합시다. 그리고 현재 용량을 capacity라고 해봅시다. V는 그 물건의 가치, W는 그 물건의 용량이라고 친다면 우리는 이런 식을 쓸 수 있습니다.

 knapsack(pos + 1, capacity - items[pos][W]) + items[pos][V]

 

knapsack이라는 함수는 현재 물건 이후 가장 큰 값을 반환합니다. 그러니까 당연히 용량(capacity)는 그 물건의 무게(items[pos][W])만큼 줄어들 것이고, 그 반환된 가장 큰 값에서 현재 물건의 가치를 더함으로써 지금 이 물건을 훔쳤을때 얻을 수 있는 값을 얻을 수 있습니다.

 

 

2) 훔쳐가지 않을 때

그리고 또 그냥 그 물건을 안가져갈 수도 있습니다. 그럴때는 현재 무게가 그대로 유지되면서 다음 물건을 고려하는 겁니다.

 

그러니 아래의 식이 가능합니다.

 

knapsack(pos + 1, capacity )

 

 

1)훔쳐갈 경우와 2)훔쳐가지 않을 경우 중에서 가장 큰 값이 우리가 원하는 답이 되는 것이죠.

 

코드

이런 프로그램을 구현한 것이 바로 아래 소스 코드입니다.

 

#include <stdio.h>
#define W 0
#define V 1
#define N 5
#define MAX(a,b) a>b ? a:b;

int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = 0;
	if (items[pos][W] <= capacity) //지금 pos의 물건을 훔칠 수 있을때
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
        //지금 pos의 물건을 훔치지 않을때와 ret 중에 큰 값
	ret = MAX(ret, knapsack(pos + 1, capacity)); 
	return ret;
}
int main() {
	int capacity = 15;
	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

답은 원하는 결과대로 나옵니다.

 

허나 이런 무식한 해결방법을 원한 것을 아닙니다.

만약 물건의 수가 많게 된다면 답을 구하기 전에 도둑은 감방으로 직행하게 될 것입니다. knapsack함수는 분명 같은 값을 여러번 중복해서 계산합니다. knapsack(pos,capacity)에서 같은 pos와 같은 capacity가 이전에 계산했었음에도 불구하고 또 다시 한번 더 계산한다는 것이죠.

 

그래서 DP가 사용됩니다. 단지 계산된 결과를 기억하고 있다가, 같은 계산을 수행할때 바로 값을 반환해주면 됩니다.

 

아래의 수정된 코드처럼 말입니다.

 

#include <stdio.h>
#include <stdlib.h>
#define W 0
#define V 1
#define N 5
#define MAX_CAPACITY 1000
#define MAX(a,b) a>b ? a:b;

int dp[N][MAX_CAPACITY];
int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = dp[pos][capacity];
	if (ret != -1) return ret;
	if (items[pos][W] <= capacity)
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
	ret = MAX(ret, knapsack(pos + 1, capacity));
	return dp[pos][capacity]=ret;
}
int main() {
	int capacity = 15;
	memset(dp, -1, sizeof(dp));

	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

우선 dp라는 2차원 배열을 -1로 셋팅합니다. 그리고 dp[pos][capacity]가 -1이 아니면 바로 그 값을 반환합니다. 배낭문제에서 음수는 나올 수 없습니다. 만약 계산되지 않은 값이라면 계산 후 dp[pos][capacity]에 값을 넣어주는 것입니다. 기억하고 있습니다.

 

결국 도둑은 가장 비싼 물건들을 훔쳐갈 수 있었지만, CCTV에 걸려 감방에 끌려가게 됩니다. 그걸 도와준 저도 같이 갑니다.