[백준] 12865번 - 평범한 배낭

 

12865번: 평범한 배낭

 

 

 

 

2차원 배열인 dp[][]에 계산결과를 저장하며 최댓값을 구하는 동적 계획법 활용 가능 문제이다.

 

문제 풀이에 앞서 해당 문제의 유형에 대해 간략하게 정리하겠다. 12865 배낭문제와 같은 문제를 냅색(knapsack problem)문제라고 부른다. 가능한 조합 중에서 어떤 수치의 합의 최대값을 구하는 조합 최적화 문제의 일종이다.

 

이러한 냅색문제, 통칭 '배낭 문제'는 분할이 가능한 문제와 분할할 수 없는 문제로 나눌 수 있다. 이번 문제를 예로 들자면 만약 준서가 싸는 짐이 kg단위로 분할 가능하다면 5kg을 담을 수 있는 배낭에 10kg짜리 짐을 절반으로 분할하여 배낭에 담을 수 있다. 이 경우 분할이 가능한 문제라고 부른다. 반면 준서가 배낭에 싸는 짐이 금괴와 같이 분할할 수 없는 경우 5kg을 담을 수 있는 배낭에 10kg짜리 금괴를 담을 수 있는 방법은 없다. 이 경우 분할이 불가능한 문제라고 부른다.

 

 

 

만약 이번 문제에서 준서가 배낭에 넣고자 하는 짐이 분할 가능한 상태라면 그리디 알고리즘으로 해결할 수 있다.

 

이차원 배열 wv은 무게 당 가치의 크기 (가치 / 무게)에 따라 내림차순 정렬되어 있고 wv[i][0] 은 해당 짐의 무게, wv[i][1]은 해당 짐의 가치이다. 

int weight = 0; // 현재 배낭에 담긴 짐들의 무게 합
int value = 0; // 현재 배낭에 담긴 짐들의 가치 합

for (int i=0; i<N; i++) {
	if (weight + ww[i][0] <= W) {
    	value += wv[i][0] * wv[i][1];
        weight += wv[i][0];
    }
    else {
    	value += (W - weight) * wv[i][1];
        break;
    }
}

 

 

 

 

그러나 이번 문제의 경우 분할 할 수 없는 경우이다. 이 경우에는 다음과 같은 일련의 과정을 동적 계획법에 적용하여 문제를 해결한다. 

 

i) i 번째 물건을 배낭에 넣는 것을 고려할 때, 배낭의 최대 용량이 j 일 때의 가치 합의 최대가 dp[i][j]인 이차원 배열을 생성한다.

dp[][]  (짐무게 \배낭용량)	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6(1)	0
4(2)	0
3(3)	0
5(4)	0

 

ii) 만약 i번 째 짐의 무게가(w[i]) 현재의 배낭 용량(W)보다 크다면 해당 짐은 배낭에 넣을 수가 없다. 이 경우 i-1번째 짐까지 고려한 가치의 최대값이 dp에 들어간다.

ii) 만약 i번 째 짐의 무게가 현재의 배낭 용량보다 작거나 같으면 다음 두 경우 중 더 큰 값이 dp에 들어간다.

ii-1) i-1번 째 짐을 배낭 용량이 W - w[i-1] 인 경우 최대 가치에 i번 째 짐을 넣은 가치의 합

ii-2) i번 째 짐을 넣지 않고 i-1번째 짐까지 고려한 가치 합의 최대

 

위의 논리로 위 표를 채운 결과는 다음과 같다.

dp[][]  (짐무게 \배낭용량)	0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0	0
6(1)	0	0	0	0	0	0	13	13
4(2)	0	0	0	0	8	8	13	13
3(3)	0	0	0	6	8	8	13	14
5(4)	0	0	0	6	8	12	13	14

 

 

이를 코드로 구현한 것이다.

static int knapsack (int obj, int bag) { // obj은 현재 넣으려는 짐, bag는 배낭의 용량
        
    if (dp[obj][bag] == null) {

        if (W[obj] > bag) // 현재 넣으려는 짐 무게가 배낭 용량보다 큰 경우
        
            dp[obj][bag] = knapsack(obj-1, bag); // 짐을 넣지 못하므로 이전 짐까지 넣은 가치 합의 최대가 그대로 들어간다.
        
        else 			  // 현재 넣으려는 짐 무게가 배낭 용량보다 작거나 같은 경우
        
        	// 이전 짐까지 넣은 가치의 최대 합과 
            // 배낭에서 현재 짐의 무게만큼 뺀 상태에서 가치의 최대 합에 현재 넣으려는 짐의 가치를 합한 값
            // 두 값 중 더 큰 값을 dp에 저장한다. 
            dp[obj][bag] = Math.max(knapsack(obj-1, bag) 
                                    , knapsack(obj-1, bag-W[obj])+V[obj]);
    }

    return dp[obj][bag];
}

 

 

 

 

전체 코드

 

TopDown 방식

import java.util.*;
import java.io.*;

public class Main {
    
    static int[] W, V;
    static int N, K;
    
    static Integer[][] dp;
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
       	StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        W = new int[N+1];
        V = new int[N+1];
        dp = new Integer[N+1][K+1];
        
        for (int i=0; i<K+1; i++) dp[0][i] = 0;
        for (int i=0; i<N+1; i++) dp[i][0] = 0;
        
        
        for (int i=1; i<N+1; i++) {
            st = new StringTokenizer(br.readLine());
            W[i] = Integer.parseInt(st.nextToken());
            V[i] = Integer.parseInt(st.nextToken());
        }
        
        System.out.println(knapsack(N, K));
        
        br.close();
    }
    
    static int knapsack (int obj, int bag) {
        
        if (dp[obj][bag] == null) {
            
            if (W[obj] > bag) 
                dp[obj][bag] = knapsack(obj-1, bag);
            else 
                dp[obj][bag] = Math.max(knapsack(obj-1, bag)
                                        , knapsack(obj-1, bag-W[obj])+V[obj]);
        }
        
        return dp[obj][bag];
    }
}

 

 

 

BottomUp 방식

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        int[][] backpack = new int[N+1][2];
        int[][] dp = new int[N+1][K+1];
        
        for (int i=1; i<=N; i++) {
            st = new StringTokenizer(br.readLine());
            backpack[i][0] = Integer.parseInt(st.nextToken());
            backpack[i][1] = Integer.parseInt(st.nextToken());
        }
        
        
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=K; j++) {
                if (backpack[i][0] <= j) dp[i][j] 
                    = Math.max(dp[i-1][j], dp[i-1][j-backpack[i][0]] + backpack[i][1]);
                else dp[i][j] = dp[i-1][j];
            }    
        }
        
        System.out.println(dp[N][K]);
        
        br.close();
    }
}