동적 설계법(DP : Dynamic Programming)이란 알고리즘 설계 기법의 하나로서 프로그래밍 콘테스트에서 매우 자주 출제됩니다. 


탐색 메모화 및 동적 설계법



베낭문제(Knapsack problem)

무게와 가격이 각각 wi, vi인 n개의 물건이 있습니다. 무게의 총합이 W를 초과하지 않도록 물건을 선택했을 때 가각 총합의 최대치를 구하세요.

예)

입력

n = 4

(w, v) = {(2, 3), (1, 2),(3, 4), (4, 9)}

W = 7


출력 

14 ( 4, 0, 2 번 물건을 고른다)



이것은 배낭 문제라고 불리는 유명한 문제입니다. 이 문제는 어떻게 접근하면 좋을까요? 우선 일반적인 방법으로 생각해보면 (넣는다/안 넣는다) 이 두 가지 상태로 분기하면서 탐색하는 방법을 생각할 수 있습니다. 


코드로 보면 다음과 같습니다.



public class Knapsack_Recursive1 {
int[] w = {2, 1, 3, 4};
int[] v = {3, 2, 4, 9};
int MAX_ITEM_LENGTH = w.length;
int MAX_ITEM_WEIGHT = 7;


int cnt = 0;
// i : 아이템의 인덱스
// j : 무게의 총합. MAX 값으로 시작해서 아이템을 선택하여 넣는다 이면 해당 아이템의
// 무게를 뺀다.
public int recursive(int i, int j){
cnt++;
int res = 0;
if(i==MAX_ITEM_LENGTH){
res = 0;
}else if(j<w[i]){
// 이 물건은 무게의 총합보다 크므로 패쓰한다.
res = recursive(i + 1, j);
// 다음번 인덱스로 넘기고, 무게의 총합은 변하지 않는다.
}else {

// 넣었을 때, 넣지 않았을 때를 조사한다.
// max(넣지 않았을 때, 넣었을 때)
// 넣었을 때의 수식을 말로 풀어쓰면
// 현재 아이템의 값을 더하고, 무게를 제거한다.
res = max(recursive(i+1, j), recursive(i+1, j-w[i])+v[i]);
}
return res;
}

int max(int a, int b) {
return Math.max(a, b);
}

@Test
public void test(){
System.out.println(recursive(0, MAX_ITEM_WEIGHT));//14
System.out.println(cnt);//28
}
}



이 방법은 탐색의 깊이가 n이고, 각 깊이에 대해 2회 분기처리 하므로 최악의 경우 O(2^n) 시간이 걸리므로 n 값이  크면 지나치게 많은 시간이 걸리므로 좋은 방법이라 할 수 없습니다.


메모화 테이블을 활용할 수 있다.

mt[아이템 갯수][최대 담을 수 있는 무게]

테이블을 만든다.

그리고 이미 계산한 값이라면 계산된 값을 리턴하는 것이다.




public class Knapsack_Recursive2 {
int[] w = {2, 1, 3, 4};
int[] v = {3, 2, 4, 9};
int MAX_ITEM_LENGTH = w.length;
int MAX_ITEM_WEIGHT = 7;
// memorize table
int[][] mt = new int[MAX_ITEM_LENGTH+1][MAX_ITEM_WEIGHT+1];

int cnt = 0;
// i : 아이템의 인덱스
// j : 무게의 총합. MAX 값으로 시작해서 아이템을 선택하여 넣는다 이면 해당 아이템의
// 무게를 뺀다.
public int recursive(int i, int j){

cnt++;
// 함수에 같은 parameters가 전달된다면 같은 결과가 나오므로
// 이미 조사한적이 있는 parameters라면 이전 값을 활용한다.
if(mt[i][j]>0) return mt[i][j];

int res = 0;
if(i==MAX_ITEM_LENGTH){
res = 0;
}else if(j<w[i]){
// 이 물건은 무게의 총합보다 크므로 패쓰한다.
res = recursive(i + 1, j);
// 다음번 인덱스로 넘기고, 무게의 총합은 변하지 않는다.
}else {

// 넣었을 때, 넣지 않았을 때를 조사한다.
// max(넣지 않았을 때, 넣었을 때)
// 넣었을 때의 수식을 말로 풀어쓰면
// 현재 아이템의 값을 더하고, 무게를 제거한다.
res = max(recursive(i+1, j), recursive(i+1, j-w[i])+v[i]);
}
mt[i][j]=res;
return res;
}

int max(int a, int b) {
return Math.max(a, b);
}


void initMt(){
for(int i=0;i<MAX_ITEM_LENGTH;i++)
for(int j=0;j<MAX_ITEM_WEIGHT;j++)
mt[i][j]=-1;
}
@Test
public void test(){
System.out.println(recursive(0, MAX_ITEM_WEIGHT));//14
System.out.println(cnt);//26
}
}






이렇게 함으로해서 recursive 함수를 28번에서 26번 방문하는 것으로 줄었다.

최악의 경우에도 O(n*W) 로 되었다.


메모화 테이블에 주목해 보도록하겠다. 

다음 글에서 계속.


예제 출처) 프로그래밍 콘테스트 챌린징(http://www.roadbook.co.kr/49)

+ Recent posts