Clean Code hochulshin.com

Algorithm - 0-1 Knapsack

2015-08-15

문제

무게 W를 감당할 수 있는 배낭이 있을때 n개 종류의 물건을 선택해서 넣을 수 있다. 각 물건은 무게와 가격이 각각 다르다. 최대 가격이 되기 위해 어떤 물건을 선택해야 하는지 알아내는 것이 Knapsack 문제이다. Knapsack문제는 2가지가 있는데 하나는 0-1 Knapsack으로 물건을 자를 수가 없다는 것이고, 다른 하나는 Fraction Knapsack으로 물건을 자를 수 있다는 것이다.

Fraction Knapsack

Fraction Knapsack문제는 물건의 가격을 무게로 나누어 무게 대비 가격이 비싼 순서로 물건을 정렬해서 넣으면 쉽게 해결할 수 있다. 남은 배낭이 감당할 수 있는 무게보다 물건의 무게가 많이 나가면 잘라서 넣으면 된다.

0-1 Knapsack

0-1 Knapsack 문제는 물건을 자를 수 없기 때문에 물건, 물건의 무게, 물건의 가격, 배낭의 남은 용량을 모두 고려해야 한다.

아이디어

물건을 넣을지 말지를 결정하는 기준은 넣었을 때 배낭의 최대 가격과 넣지 않았을 때의 최대 가격 중 큰 것이 무엇이냐이다. 예를 들어 배낭이 10kg을 감당하고, 필통이 1kg, 1만원, 곰인형이 4kg, 10만원, 선물이 11kg, 100만원이라고 하자. 처음 배낭이 10kg이고, 곰인형은 배낭에 넣을 수 있다. 곰인형을 넣자라는 선택을 하면, 최대 가격은 10만원 + 6k에 남은 물건을 가지고 넣을 수 있는 최대 가격이 된다. 그렇게 되면 6kg에 남은 2가지 물건을 고려했을 때 넣을 수 있는 최대 가격 문제가 부분문제가 된다. 곰인형을 넣지 말자라는 선택을 하면, 최대 가격은 0만원 + 10kg에 남은 물건 물건을 가지고 넣을 수 있는 최대 가격이 된다. 그렇게 되면 10kg에 남은 2가지 물건을 고려했을 때 넣을 수 있는 최대 가격 문제가 부분문제가 된다.

이를 일반화 하면 다음과 같다.

  • W: 배낭이 감당할 수 있는 무게 (용량)
  • (vi, wi): 물건 i가 가지는 가격과 무게
  • K[i, w]: 남은 배낭 무게가 w일때 물건 1~i까지 고려한 경우의 최대 가격
K[i, w] = 0 if i = 0 or w = 0 //선택할 물건이 남아있지 않거나 배낭에 넣을 수 있는 무게가 0
        = K[i-1, w] if wi>w //물건 i가 너무 무거워서 배낭에 넣을 수 없음
        = max(vi + K[i-1, w-wi], K[i-1, w])//물건을 넣었을때와 넣지 않았을때의 가격 중 최대를 택함 
                                           //vi + K[i-1, w-wi]: 넣었을 때, K[i-1, w]: 넣지 않았을 때 

Iteration을 이용한 구현

Pseudo 코드

위 알고리즘을 Pseudo 코드로 표현하면 다음과 같다.

function(){
	for i in 0->n{ //초기화
		k[i, 0] <- 0
	}
	for w in 0->n{ //초기화
		k[i, w] <- 0
	}
	for i in 1 -> n{
		for w in 1 -> W{
			if(wi >w) //물건 i가 너무 무거워서 배낭에 넣을 수 없음
				K[i,w] <- K[i-1,w]
			else //물건을 넣었을때와 넣지 않았을때의 가격 중 최대를 택함 
				K[1,w] <- max(k[i-1, w-wi] + vi, K[i-1,w])
		}
	}
	return K[n,W] //무게 W에 물건 n일때의 최대 값 반환
}

C 코드

위의 배낭 10kg과 필통, 곰인형, 선물의 경우를 테스트 코드로 해보자.

#include <stdio.h>

int K[5][21]; //num of objects, weight
int knapsack(int n, int W, int price[], int weight[]){
    for(int i=0;i<=n;i++){
        K[i][0] = 0;
    }
    for(int w=0;w<=W;w++){
        K[0][w] = 0;
    }
    for(int i=1;i<=n;i++){
        for(int w=1;w<=W;w++){
            if(weight[i]>w)
                K[i][w] = K[i-1][w];
            else{
                int selected_val = K[i-1][w-weight[i]] + price[i];
                int unselected_val = K[i-1][w];
                K[i][w] = selected_val > unselected_val?selected_val:unselected_val;
            }
        }
    }
    return K[n][W];
}

int main(){
    int price[4] = {0, 10, 1, 100};
    int weight[4] = {0, 4, 1, 11};
    int Weight = 10; //베낭 10kg
    int max_val = knapsack(3, Weight, price, weight);
    printf("max price: %d", max_val);
    return 0;
}

Recursion을 이용한 구현

위의 아이디어를 반복이 아닌 recursion으로 구현해보자. K[i, w]가 반복적으로 계산되기보다는 계산의 과정으로만 쓰이기 때문에 memoization기법을 적용할 필요는 없다.

C 코드

#include <stdio.h>

int knapsack(int i, int w, int price[], int weight[]){
    if(i == 0 || w == 0)
        return 0;
    int unselected_val = knapsack(i-1, w, price, weight);
    if(weight[i] > w){
        return unselected_val;
    }
    int selected_val = knapsack(i-1, w-weight[i], price, weight) + price[i];
    int max_val = selected_val > unselected_val?selected_val:unselected_val;
    return max_val;
}

int main(){
    int price[4] = {0, 10, 1, 100};
    int weight[4] = {0, 4, 1, 11};
    int Weight = 10; //베낭 10kg
    int max_val = knapsack(3, Weight, price, weight);
    printf("max price: %d", max_val);
    return 0;
}

Comments