BOJ 12865 평범한 배낭

 

이 문제는 다이나믹 프로그래밍(동적계획법, DP) 문제이다. 나는 평소에 Top-down 방식으로 구현하는 것이 익숙해, bottom-up 방식의 구현을 잘 구현하지 못한다.. 그래서 bottom-up 방식으로도 구현하는 연습해야겠다고 생각해서 오랜만에 DP 문제를 찾았다.

 

DP 는 큰 문제를 작은 문제로 나누어푸는데, 분할정복과 다른 점은 DP는 작은 문제로 나누어 풀 때, 작은 문제들의 결과가 항상 동일하고 반복이 일어난다. 작은 문제들의 일정한 결과를 이용해 큰 문제를 해결하는 과정이라고 볼 수 있다. 따라서, 작은 문제들의 일정한 결과 값을 저장하기 위해 Memoization 을 하며, 같은 작은 문제를 만났을 때 이미 한 번 해결했던 문제라면 저장해놓은 값을 이용해 반복 수행 횟수를 줄일 수 있다.

 

Top-Down

 

먼저  Top-Down 방식의 풀이에서는, DP를 다음과 같이 정의한다.

dp[p][q] = q 만큼의 무게를 들 수 있을 때,  p 번째의 물건을 선택해 얻을 수 있는 최대의 가치

이렇게 정의하면, 

dp[p][q] = max( dp[p-1][q] ,  dp[p-1][ q - weight[p] ] + value[p] )

처럼 p 번째 물건을 선택하지 않은 경우와 선택한 경우 모두 고려할 수 있다.

 

기저조건(재귀의 탈출조건) 은 p 번째 물건이 0~n-1 번의 물건 개수 범위를 넘어설 때이다. Top-down 방식의 구현은 다음과 같다.

 

int solve(int p, int q){
    if(p == -1) return 0;
 
    int& ret = dp[p][q];
    if(ret != 0)
        return ret;
    
    int h = solve(p-1, q);
    if(q - arr[p][0] >= 0)
        h = max( h, solve(p-1, q-arr[p][0]) + arr[p][1] );
 
    return ret = h;
}

 

 

Bottom-Up

 

다음은 반복문을 이용해 구현하는 Bottom-Up 방법으로 풀어보면, 마찬가지로 2차원의 배열이 필요하다. 익숙치 않아서 시간이 꽤 걸렸다.

DP의 정의는 같으며, 내가 구현한 방식은 다음과 같다.

 

    for(int i=1;i<=n;i++){
        dp[i][arr[i-1][0]] = arr[i-1][1];
        for(int w=0; w<=k; w++){
            dp[i][w] = dp[i-1][w];
            if(w - arr[i-1][0] >= 0){
                dp[i][w] = max(dp[i][w], dp[i-1][w-arr[i-1][0]] + arr[i-1][1]);
            }
        }
    }
    printf("%d\n", dp[n][k]);

 

위 문제의 예제는 너무 쉽기 때문에, 다음 예제를 이용해 설명하면 다음과 같다.

4 20
6 13
2 5
3 9
10 20

4개의 물건이 있으며 무게는 7 까지 가능하기 때문에, 배열은 dp[4][7] 크기가 필요하다.

dp 에는 i 번째 물건까지 고려했을 때, w 무게에서의 최대 가치를 저장한다. 

즉,

 

무게는 0~20 까지 모두 출력되었다.  dp[1] 은 첫 번째 물건만을 고려했을 때 까지의 가능한 최대 가치를 보여주며, dp[2]는 두 번째 물건 까지 고려했을 때의 가치이다. 두 번째 물건의 무게는 2로 인덱스 2번 부터 무게 5가 채워지며, 무게 6부터는  첫 번째 물건의 가치가 더 크기 때문에 13이 유지되며, 두 무게를 합친 8 무게부터는 두 가치를 합친 값이 저장되기 시작한다. 

 

 

전체 소스 코드

#include<stdio.h>
 
int n,k;
int arr[101][2], dp[101][100001];
 
int inline max(int a,int b){ return a>b? a:b;}
int solve(int p, int q){
    if(p == -1) return 0;
 
    int& ret = dp[p][q];
    if(ret != 0)
        return ret;
    
    int h = solve(p-1, q);
    if(q - arr[p][0] >= 0)
        h = max( h, solve(p-1, q-arr[p][0]) + arr[p][1] );
 
    return ret = h;
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d %d",&arr[i][0], &arr[i][1]);
    }
 
    // int ans = solve(n-1, k);
    // printf("%d\n", ans);
 
    for(int i=1;i<=n;i++){
        dp[i][arr[i-1][0]] = arr[i-1][1];
        // printf("dp[%d] : ",i);
        for(int w=0; w<=k; w++){
            dp[i][w] = dp[i-1][w];
            if(w - arr[i-1][0] >= 0){
                dp[i][w] = max(dp[i][w], dp[i-1][w-arr[i-1][0]] + arr[i-1][1]);
            }
            // printf("%2d ", dp[i][w]);
        }
        // printf("\n");
    }
    printf("%d\n", dp[n][k]);
 
    return 0;
}