알고리즘: 되추적(BackTracking)을 이용한 0 - 1 배낭채우기 문제(0- 1 knapsack problem) 공부하기

 

이전에는 동적계획법을 이용하여 0-1 knapsack 문제에 대해 다루었다. 

 

알고리즘: 배낭채우기(knapsack problem) 공부하기!(0-1 knapsack problem)

 

 

이번 포스팅은 좀 더 효율적인 0-1 knapsack problem 알고리즘에 대해 알아본다. 

 

기존의 0-1 knapsack problem은 상태공간트리에서 되추적을 이용하였다.

 

이 문제는 최댓값을 구하는 최적화 문제이기때문에 검색이 완전히 끝나기 전까지는

마디가 해답을 포함하고 있는지 알지 못한다. 

 

따라서 되추적을 조금 다른 방식으로 한다.

 

이를 테면, 지금까지의 최고 해답보다 값어치의 총액이 크다면 현재의 총액으로 값을 갱신한다.

(이전의 포스팅에서 살펴보았던 되추적은 필요한 마디만 찾은 후 되추적을 끝냈다)

 

 

 

기존의 0-1 knapsack problem에서 유망하지 않다고 알려주는 표시를 살펴보자

 

- weight를 어떤 마디까지의 무게 합이라고 할때 weight >= W였다. 

- profit을  어떤 마디까지의 이익 합이라고 할때 더 높은 profit을 이용하였다. 

 

 

 

하지만 이로써는 유망한 마디라고 하기 부족하다. 좀 더 알아내기 어려운 표시를 이용해보자 

 

새로운 0-1 knapsack problem을 풀기 위해 추가적으로 totweight와 bound를 정의한다.

 

- totweight: 지금까지의 무게 합 + 앞으로 넣을 수 있는 무게합

- bound: 지금까지 profit합 + 앞으로 더해질 profit + partial profit이라 하자

 

 

 

 

 

< 알고리즘 스케치 >

 

- bound와 totweight를 profit과 weight로 초기화한다.

- 탐욕적으로 아이템을 취한다.

- 과정 1, 2를 totweight가 W를 초과하게 되는 아이템을 잡을 때까지 반복한다.

- 남은 공간이 허용하는 무게만큼 마지막 아이템의 일부분을 취하고,

그 일부분에 해당하는 profit을 bound에 더 한다.

- 마디가 수준 i에 있다고 하고 수준 k에 있는 마디에서 총 무게가 W를 넘는다고 할때

 

 

 

- bound <= maxprofit 일때 그 노드는 유망하지 않다. 

 

 

(0, 0) 노드에서는 maxprofit = 0

profit = 0

weight = 0

 

 

깊이 우선순위로 각 마디를 방문하여 다음을 수행한다. 

 

1. 그 마디의 profit과 weight를 계산한다.

2. 그 마디의 bound를 계산한다.

3. weight < W이고, bound > maxprofit이면 검색을 계속한다. 그렇지 않다면 되추적한다. 

 

 

 

 

무슨 말인지 이해하기 어려우므로 예시를 가지고 이해해보자.

 

다음은 무게당 가격순으로 미리 정렬해놓았다. 이때의 상태공간 트리를 구해보자 

 

 

 

 

 

 

해답) 

 

결론적으로  상태공간 트리는 위와 같은데 어떻게 이런 결과가 나왔을까?

 

 

다음과 같은 절차를 거치면서 알아보자

 

 

1. maxprofit = 0 으로 설정

 

 

 

2. 마디 (0, 0)을 방문한다.

 

a) 그 값어치와 무게를 계산한다.

profit = 0

weight = 0

 

 

b) totweight와 bound를 계산해보자. 

 

2 + 5 + 10 > W이므로 3번째 아이템을 취하면 무게 합이 W를 넘는다. 

 

k = 3이므로 bound, totweight 공식에 의해

 

totweight = weight + 0 + 2 + 5 = 7

bound = profit + 40 + 30 + (16 - 7) x 50/10 = 115

 

 

c) 0(무게 값) < W 이고 115(bound) > 0(maxprofit)이므로 이 마디는 유망하다고 결정한다. 

 

 

 

 

3. 마디 (1, 1)을 방문한다. 

 

a) 그 값어치와 무게를 계산한다.

profit = 0 + 40 = 40

weight = 0 + 2 = 2

 

profit이 40이므로 기존의 maxprofit인 0 보다 크다.

maxprofit을 40으로 갱신한다. 

 

 

b) totweight와 bound를 계산해보자. 

 

2 + 5 + 10 > W이므로 3번째 아이템을 취하면 무게 합이 W를 넘는다. 

 

k = 3이므로 bound, totweight 공식에 의해 

totweight = weight  + 2 + 5 = 7

bound = profit + 30 + (16 - 7) x 50/10 = 115

 

 

c) 2(무게 값) < W 이고 115(bound) > 40(maxprofit)이므로 이 마디는 유망하다고 결정한다.

 

 

 

 

4. 마디 (2, 1)을 방문한다.

 

a) 그 값어치와 무게를 계산한다.

profit = 40 + 30 = 70

weight = 2 + 5 = 7

 

profit이 70이므로 기존의 maxprofit인 40 보다 크다.

maxprofit을 70으로 갱신한다. 

 

 

b) totweight와 bound를 계산해보자. 

 

2 + 5 + 10 > W이므로 3번째 아이템을 취하면 무게 합이 W를 넘는다. 

 

k = 3이므로 bound, totweight 공식에 의해 

totweight = weight  + 0 = 7

bound = profit + (16 - 7) x 50/10 = 115

 

 

c) 7(무게 값) < W 이고 115(bound) > 70(maxprofit)이므로 이 마디는 유망하다고 결정한다.

 

 

 

 

5. 마디(3, 1)을 방문한다.

 

a) 그 값어치와 무게를 계산한다.

profit = 70 + 50 = 120

weight = 7 + 10 = 17

 

weight > W이므로 maxprofit값은 변하지 않는다.

 

 

b) weight > W이므로 이 마디는 유망하지 않다고 결정한다.

 

c) 이 마디는 유망하지 않으므로 이 마디의 한계는 계산하지 않는다.

 

 

 

 

6. 마디 (2, 1)로 되추적

 

 

 

 

7. 마디 (3, 2)을 방문한다.

 

a) 아이템 3은 포함하지 않으므로 

profit = 70

weight = 7

maxprofit = 70

 

 

b) totweight와 bound를 계산해보자. 

 

2 + 5 + 0 + 5 > W이므로 4번째 아이템을 취해도 무게 합이 W를 넘지않으므로 k =5이다. 

 

k = 5이므로 bound, totweight 공식에 의해 

bound = profit + 10 = 80

 

 

c) 7(무게 값) < W 이고 80(bound) > 70(maxprofit)이므로 이 마디는 유망하다고 결정한다.

 

위의  과정을 모든 노드에 대해서 반복하여 되추적한다. 

 

이제 이 알고리즘을 수도코드를 통해서 구현하면 다음과 같다. 

 

 

 

 

 

<pseudo 코드>

void knapsack (index i, int profit, int weight) {
	if (weight <= W && profit > maxprofit) { // 지금까지 최고의 답
		maxprofit = profit;
		numbest = i; 
		bestset = include; 
	}
    
	if (promising(i, profit, weight)) {
		include[i+1] = “YES”; // Include w[i+1]
		knapsack(i+1, profit+p[i+1], weight+w[i+1]);
		include[i+1] = “NO”; // Not include w[i+1]
		knapsack(i+1, profit, weight);
	}
}

 

 

bool promising(index i, int profit, int weight) {
	index j, k; 
	int totweight; 
	float bound;
	if (weight >= W) return FALSE;  //자식마디로 확장할 수 있을 때만 유망하다.
	else {							//자식마디에 쓸 공간이 남아 있어야 한다. 
		j = i+1;
	bound = profit; 
	totweight = weight;
	while ((j <= n) && (totweight +w[j] <= W)) {  //가능한 많은 아이템을 취한다. 
		totweight = totweight + w[j]; 
		bound = bound + p[j];
		j++
	}
	k=j;  		
	if (k <= n)  // k째 아이템의 일부분을 취함
		bound = bound +(W–totweight)*p[k]/w[k];
	
    return bound > maxprofit;
}
}

 

 

 

이 전의 0-1 배낭채우기에서 동적계획법을 이용하여 최악의 경우 엔트리 갯수는

였다.

 

되추적을 이용한 최악의 경우는 

이다.

 

 

추가적인 한계 nW덕분에 동적계획 알고리즘이 더 좋은 것처럼 보일 수 있다.

 

그러나 실제로는 되추적 알고리즘에서 최악의 경우를 따지면 검사 횟수를 얼마나

절약하게 되는지 별로 반영하지못한다.

 

고려해야할 사항이 너무 많아서 이 두 알고리즘의 상대적인 효율을 이론적으로 분석하기는 어렵다.

 

이런 경우는 많은 사례를 가지고 알고리즘을 직접 실행해보고, 어떤 알고리즘이 더 좋은지 알아보아 비교할 수 있다.

 

Horowitz와 Sahni는 이 실험을 했고 몬테칼로 알고리즘을 통해서 

되추적 알고리즘이 동적계획알고리즘보다 보통 더 효율적임을 알아냈다. 

 

즉, 되추적 알고리즘을 이용한 0-1 knapsack이 웬만해서는 더 효율적!

 

 

 

출처 : Foundations of Algorithms, Using C++ Pseudocode