동적 설계법 - 값을 기억해서 재활용한다. -2 메모화 테이블

동적 설계법 - 값을 기억해서 재활용한다.  메모화 테이블

이전 글에서 메모화 테이블을 보고 왔다.

메모화 테이블은 간단하게 말해 이전 값을 기억해서 불필요한 연산을 줄이는 것이다. 하지만 이것을 잘만 이용한다면 동일한 문제에 대해서 더욱더 간결하게 해결 할 수 있다.

int[] w = {2, 1, 3, 4};

int[] v = {3, 2, 4, 9};

mt[i][j]

i : 아이템의 인덱스

j : 무게의 총합.

메모화 테이블

mt[i][j] 는 함수 recursive 의 정의보다 i 번째 이후의 무게의 총합이 j 이하가 되도록 고른 경우의 가격 총합이 최대치가 되게 하고 있다.

이를 수식으로 보면

mt[i+1][j]=mt[i][j] | (j<w[i])

mt[i+1][j]=max(mt[i][j], mt[i][j-w[i]]+v[i]) | (그 외)

mt[i][j] 넣지 않았을 때 : 넣지 않았으므로 현재 무게와 이전 값을 유지한다.

mt[i][j-w[i]]+v[i]) 넣었을 때. 넣게 되면 이전 무게의 값과 현재의 값을 합친다.

코드로 보겠다.

public class Knapsack_MemTable1 {
    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;

    void solve(){
        for(int i=0;i<MAX_ITEM_LENGTH;i++){

            for(int j = 0;j<=MAX_ITEM_WEIGHT;j++){
                cnt++;
                if(j<w[i]){
                    mt[i+1][j] = mt[i][j];
                }else{
                    mt[i+1][j] = max(mt[i][j], mt[i][j-w[i]]+v[i]);
                    /*
                    더하는 값은 현재 인덱스의 이전 무게 인덱스의 벨류.
                    즉 같은 인덱스는 사용하지 않는다. 왜냐하면 인덱스는 한가지만 사용하기 때문이다.
                     */
                }
            }
        }
    }

    private int max(int i, int j) {
        return Math.max(i, j);
    }
    void initMt(){
        for(int i=0;i<MAX_ITEM_LENGTH;i++)
            for(int j=0;j<MAX_ITEM_WEIGHT;j++)
                mt[i][j]=0;
    }

    @Test
    public void test(){
        initMt();
        solve();
        System.out.println(mt[MAX_ITEM_LENGTH][MAX_ITEM_WEIGHT]);//14
        System.out.println(cnt);//32
    }

}

사실 계산은 이전 포스팅의 재귀함수보다 더 많이 하고 있다. 왜냐하면 최악의 경우를 안 만났기 때문이긴 하다.

그렇지만 이처럼 2중 포문으로 돌게 되면 최악의 경우 O(n*W) 가 된다.

메모화 테이블   

int[] w = {2, 1, 3, 4};

int[] v = {3, 2, 4, 9};

mt[i][j-w[i]]+v[i]

mt[2][3] = max(mt[1][3], mt[1][3-1]+v[1]) : max(3, 3+2)

내가 계속해서 헤깔렸던 부분은 테이블이다.(읽는 사람들은 나보다 더 이해력이 좋을 것이라 믿는다.)

i/j 가 의미하는바가 계속해서 헤깔렸다.

i는 아이템이다. 해당 아이템을 넣느냐 안 넣느냐를 선택 할 아이템의 인덱스 테이블이다. 그리고 j는 최대 무게 값이다. 그리고 칸에 체워진 숫자는 더해진 값(v)이다.

예제 출처) 프로그래밍 콘테스트 챌린징(http://www.roadbook.co.kr/49) - 좋은 책임에는 확실하나 오타가 너무 많아서 중요한 부분에서 이해하기 어려운 부분이 많다. 

이 곳에 올리는 것에는 책에서 나온 잘못된 그림과 오타를 수정해서 올린 것 입니다.