[lecture]5주차.동적계획 알고리즘_배낭 문제

수업을 듣고 정리한 내용입니다.

배낭 문제는 0-1 배낭 문제라고 말하기도 하는데, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi가 주어지고, 배낭 용량이 C일 때, 최대 가지 값을 구하는 알고리즘이다. 단, 배낭에 담은 물건의 무게 합이 C를 초과하지 않으며, 각 물건은 1개씩 넣을 수 있다. 

 

이 알고리즘의 부분문제는 i=1,2,...n이고, w = 1,2, ... c라고 가정한 상황에서 K[i,w] = 물건1 부터 i까지만 고려하고, (임시)배낭의 용량이 w일 때의 최대 가치 로 둔다. 여기서 물건은 행이고, 배낭의 용량은 열이다.

Knapsack
입력 : 배낭의 용량은 c, n개의 물건과 각 물건 i의 무게 Wi와 가치 Vi, 단 i=1, 2, ... n
출력 : K[n,C]
for i = 0 to n	K[i,0] = 0	//배낭의 용량이 0
for w = 0 to C	K[0,w] = 0	//물건0은 어떤 물건도 고려하지 않은 경우
for i = 1 to n
	for  w = 1 to C			//w는 배낭의 (임시)용량
    	if (wi > w)			//물건 i의 무게가 임시 배낭 용량을 초과한 경우
        	K[i,w] = K[i-1,w]
        else				//물건 i를 배낭에 담지 않을 경우와 담을 경우를 고려한다.
        	K[i,w] = max{K[i-1,w], K[i-1,w-wi] + Vi}
return K[n,C]

좌측의 그림은 알고리즘을 좀 더 이해하기 쉽게 정리한 그림이다. 이 알고리즘의 시간 복잡도는 1개의 부분 문제에 대한 해를 구할 때의 시간복잡도는 O(1)인 점과 부분 문제 수와 배열 K의 원소수가 같기에 n*C인 점을 고려하여, O(nC)이다.