배낭 문제 (Fractional Knapsack and 0-1 Knapsack Problem)

배낭 문제에 대해 알아보도록 하자. 일반적인 배낭 문제의 정의는 다음과 같다. 

 

물건 n개의 집합 S={1,2,...,n} 와 W={w1,w2,...,wn}, P={p1,p2,...,pn}가 주어져 있다.

배낭에 이러한 물건들을 넣어 시장에 판다고 할 때, 얻을 수 있는 최대 이윤을 구한다.

 

• wi(>0) : 각 물건 i의 무게
• pi(>0) : 물건 i를 시장에서 팔았을 때 얻는 이윤
• M : 배낭의 크기(사람이 짊어질 수 있는 최대 무게)

이 문제에서 만약 물건을 쪼갤 수 있는 경우면 분수 배낭 문제(Fractional Knapsack)라 하고, 

물건을 쪼갤 수 없는 경우 0-1 배낭문제라고 한다. 

 

결론부터 말하자면 이 문제는 최적화, 즉 Optimization 문제인데, (1) 분수 배낭문제는 greedy algorithm으로 다항 시간에 풀 수 있고 (2) 0-1 배낭문제는 dynamic programming으로 의사 다항 시간(밑에서 자세히 설명함. NP-완전문제)에 풀 수 있다. 두 전략을 사용하여 푸는 방법을 모두 소개하고자 한다. 

 

(1) Greedy algorithm - fractional knapsack problem

우선, greedy algorithm은 눈 앞에 있는 최대 이익을 locally optimal하게 고르는 알고리즘이다. 따라서, 항상 optimal하다고 보장할 수 없다는 것을 알아두자. ( 0-1 knapsack 문제의 경우 greedy algorithm을 사용하면 항상 최적화 문제를 구할 수 없다. 반례 有 )

int fractional_knapsack (int num, int weight[], int profit[], float x[], int capacity){
	int cu=capacity; // 남아 있는 배낭 크기
	int max_profit=0; // 최대 이익
	int i; // index
    
	for (i=1;i<=num;i++){
		if(weight[i]>cu) break;
		x[i]=1.0;
        cu=cu-weight[i];
        max_profit=max_profit+profit[i];
        }
	if (i<=num){
		x[i]=(float)cu/weight[i];
        max_profit=max_profit+profit[i]*x[i];
        }
	return max_profit;
}

위의 알고리즘을 보면서 이해해보도록 한다. X는 solution 배열, cu는 배낭의 남은 용량을 나타내는 변수이다. 

해당 알고리즘에서 i는 단위 무게당 이윤의 내림차순으로 정렬되어 있다고 가정한다. (pi/wi>=pi+1/wi+1)

 

• a) 만약 물건의 무게가 남아 있는 배낭 크기보다 크면 loop는 종료된다. 
• b) 배낭에 더 넣을 수 있는 경우
• x[i]=1.0; // 현재 물건을 배낭에 전부 채운다. 
• cu=cu-weight[i] 값으로 남은 배낭의 크기를 갱신한다. 
• max_profit값 또한 새로 갱신한다. 
• c) 배낭에 넣을 수 있는 물건이 없을 때
• x[i]=(float)cu/weight[i]; 현재 물건을 남은 배낭의 비율만큼 채운다. 

알고리즘 fractional_knapsack에 의해 항상 분수 배낭 문제에 대한 최적의 해를 구할 수 있다.

(나중에 증명해볼 것!)