문제
무게 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;
}
近期评论