knapsack 문제

문제 제기

만약 도둑이 도둑질을 하러 가방을 들고 상점을 들어갔는데

도둑의 입장에서는 

배낭의 무게 W

물건의 가치 v 가있다면 

W를 넘어서지 않으면서 훔치는 물건의 가격이 최대가 되는 부분집합을 원할 것이다. 

우리는 여기서 어떠한 기준을 잡아서 선택할 것이다. 

1. 가격이 높은 것 부터 선택
{5, 2, 1}이 될건데 이는 {3, 4} 보다 적은 비율이다. 

 

2. 무게가 가벼운 것부터 선택

{1, 2, 3}이 선택될 건데 이는 적은 가치이다. 

 

3. 단위 무게당 가격이 높은 것 부터 선택
여기서는 
1 -> 1

2 -> 3
3 -> 3.6

4 -> 3.8

5 -> 4 가 된다. 

여기서도 당연히 안되는 결과가 나온다. 

 

순환식

opt(i, w): 배낭 용량이 w일 때 아이템 1,2,....i로 얻을 수 있는 최대 이득

경우 1: 아이템 i를 선택하지 않는 경우

  opt(i) = opt(i-1, w)

경우 2: 아이템 i를 선택하는 경우

  opt(i) = opt(i-1, w-wi) +vi -> i-1까지의 최대 이득에 i번째 vi를 더한 것이다. 

순환식을 보면 아래와 같다. 

소스 코드

#include <stdio.h>

int maxWeight = 11;
int n = 6;
int arr[6][12] = {0, };
int value[6][2] = {
	{0, 0},
	{1, 1},
	{6, 2},
	{18, 5},
	{22, 6},
	{28, 7},
};

void opt(){
	for(int i = 1; i <= n; i++){
		for(int w = 1; w <= maxWeight; w++){
			if(value[i][1] > w)
				arr[i][w] = arr[i-1][w];
			else {
				if(arr[i-1][w] < arr[i-1][w-value[i][1]] + value[i][0])
					arr[i][w] = arr[i-1][w-value[i][1]] + value[i][0];
				else
					arr[i][w] = arr[i-1][w];	
			}
		}
	}
}

int main(){
	opt();
	for(int i = 0; i <= 5; i++){
		for(int w = 0; w <= maxWeight; w++){
			printf("%d ", arr[i][w]);
		}
		printf("\n");
	}
}

 

 

결과 

시간 복잡도는 O(nW)가 된다.