[백준] 평범한 배낭 - 자바

아주구냥... 날 괴롭힌 문제

잡힐듯 안 잡힌 문제... 왜 안돼?!?! 하면서 엉엉 움

아이템 하나씩 추가될 때 무게를 1씩 늘리면서 비교하여 풀었다.

 

	1	2	3	4	5	6	7
( 6, 13 )	0	0	0	0	0	13	13
( 4, 8 )
( 3, 6 )
( 5, 12 )

물건 1 = (무게 : 6, 가치 : 13)

 

물건 1개로 짐을 싸는 방법

무게가 6부터 담을 수 있으므로 6과 7에 13만큼의 가치를 담을 수 있다. 

 

	1	2	3	4	5	6	7
( 6, 13 )	0	0	0	0	0	13	13
( 4 , 8 )	0	0	0	8	8	max( 8 + 0 , 13) = 13	max( 8 + 0 , 13) = 13
(3, 6)
(5, 12)

물건 1 = (무게 : 6, 가치 : 13)

물건 2 = (무게 : 4, 가치 :  8 )

 

물건 2개로 짐을 싸는 방법

무게가 4부터 담을 수 있으므로 4와 5에 8만큼의 가치를 담을 수 있다. 

 

무게가 6일 때 현재 추가된 물건 2인 4키로를 담으면 6 - 4 = 2키로만큼 더 담을 수 있다.

이전 행의 2키로가의 가치가  0 이므로 가치는  8  +  0  = 8

하지만 무게가 6인 이전 행의 가치인  13  보다 8의 가치가 작으므로 더 큰 13의 가치를 담을 수 있다. 

 

마찬가지로,

무게가 7일 때도 현재 추가된 물건 2인 4키로를 담으면 7 - 4 = 3키로만큼 더 담을 수 있다.

이전 행의 3키로가의 가치가  0 이므로 가치는  8  +  0  = 8

하지만 무게가 7인 이전 행의 가치인  13 과 비교하여 8의 가치가 작으므로 더 큰 13의 가치를 담을 수 있다. 

 

	1	2	3	4	5	6	7
( 6, 13 )	0	0	0	0	0	13	13
( 4, 8 )	0	0	0	8	8	13	13
( 3, 6 )	0	0	6	max( 6 + 0 ,  8 ) = 8	max( 6 + 0 ,  8 ) = 8	max( 6 + 0 , 13) = 13	max( 6 + 8 , 13) = 14
( 5, 12 )

물건 1 = (무게 : 6, 가치 : 13)

물건 2 = (무게 : 4, 가치 : 8)

물건 3 = (무게 : 3, 가치 :   6 )

 

물건 3개로 짐을 싸는 방법

무게가 3부터 담을 수 있으므로 6만큼의 가치를 담을 수 있다. 

 

무게가 4일 때 현재 추가된 물건 3인 3키로를 담으면 4 - 3 = 1키로만큼 더 담을 수 있다.

이전 행의 1키로가의 가치가  0 이므로 가치는  6  +  0  = 6

하지만 무게가 4인 이전 행의 가치인  8  보다 6의 가치가 작으므로 더 큰 8의 가치를 담을 수 있다. 

 

마찬가지로

무게가 5일 때 현재 추가된 물건 3인 3키로를 담으면 5 - 3 = 1키로만큼 더 담을 수 있다.

이전 행의 2키로가의 가치가  0 이므로 가치는  6  +  0  = 6

하지만 무게가 5인 이전 행의 가치인  8  보다 6의 가치가 작으므로 더 큰 8의 가치를 담을 수 있다.

 

무게가 6일 때 현재 추가된 물건 3인 3키로를 담으면 6 - 3 = 3키로만큼 더 담을 수 있다.

이전 행의 3키로가의 가치가  0 이므로 가치는  6  +  0  = 6

하지만 무게가 6인 이전 행의 가치인  13  보다 6의 가치가 작으므로 더 큰 13의 가치를 담을 수 있다. 

 

무게가 7일 때 현재 추가된 물건 3인 3키로를 담으면 7 - 3 = 4키로만큼 더 담을 수 있다.

이전 행의 4키로가의 가치가  8 이므로 가치는  6  +  8  =  14 

하지만 무게가 7인 이전 행의 가치인  13  보다  14 의 가치가 더 크므로 더 큰 14의 가치를 담을 수 있다.

 

	1	2	3	4	5	6	7
( 6, 13 )	0	0	0	0	0	13	13
( 4, 8 )	0	0	0	8	8	13	13
( 3, 6 )	0	0	6	8	8	13	14
( 5, 12 )	0	0	6	8	max(12,  8 ) = 12	max(12+ 0 , 13) = 13	max(12+ 0 , 14) = 14

물건 1 = (무게 : 6, 가치 : 13)

물건 2 = (무게 : 4, 가치 : 8)

물건 3 = (무게 : 3, 가치 : 6)

물건 4 = (무게 : 5, 가치 :  12 )

 

물건 4개로 짐을 싸는 방법

무게가 5부터 담을 수 있으므로 그 이전인 3, 4 무게에는 이전 행을 복사하여 6,  8 의 가치를 담는다.

12만큼의 가치를 담을 수 있다.

 

무게가 5일 때 현재 추가된 물건 4인 5키로를 담으면 5 - 5 = 0키로만큼 더 담을 수 있다.

하지만 무게가 5인 이전 행의 가치인  8  보다  12 의 가치가 크므로 더 큰 12의 가치를 담을 수 있다. 

 

무게가 6일 때 현재 추가된 물건 4인 5키로를 담으면 6 - 5 = 1키로만큼 더 담을 수 있다.

이전 행의 1키로가의 가치가  0 이므로 가치는  12  +  0  = 12

하지만 무게가 6인 이전 행의 가치인  13  보다 12의 가치가 작으므로 더 큰 13의 가치를 담을 수 있다. 

 

무게가 7일 때 현재 추가된 물건 3인 5키로를 담으면 7 - 5 = 2키로만큼 더 담을 수 있다.

이전 행의 2키로가의 가치가  0 이므로 가치는   12  +  0  = 12

하지만 무게가 7인 이전 행의 가치인  14  보다 12의 가치가 작으므로 더 큰 13의 가치를 담을 수 있다.

 

 

결론

행 마다 해당 물건이 추가됐을 때로 생각하여 더 가치있는 것으로 저장한다.

물건이 추가될 때 마다 남는 무게를 이전행의 무게로 계산하여 해당 가치와 비교한다.

int[][] dp = new int[N+1][K+1];		// 표를 저장할 2차 배열
int[] w = new int[N+1];			// 무게를 저장
int[] v = new int[N+1]; 		// 가치를 저장

for (int i = 1; i <= N; i++) {		// i = 추가된 물건
    for (int j = 1; j <= K; j++) {	// j = 계산하려는 무게
        dp[i][j] = dp[i-1][j];		// 해당 칸을 이전 행의 가치로 저장
        if (j - w[i] >= 0) {		// 무게가 남는지 확인
            dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
                                    // j-w[i] : j만큼 넣을 수 있는 가방에 i번째인 추가된 물건의 무게를 뺀 값의
                                    // dp[i-1]j-w[i] : 이전 행에서 가치를 구하여
                                    // v[i] : 추가된 물건의 가치를 더한다.
                                    // dp[i][j] : 이전 행의 가치로 저장한 값과 비교
        }
    }
}

 

왜 남은 무게를 이전 항에서 가져올까?

지금 항에서 가져오면 안되나 ?!?!

너무 헷갈렸는데,,

무게를 10까지 늘려보니 알겠더랍! ( i = 0 은 이전 항과 비교할 수 있도록 추가)

	0	1	2	3	4	5	6	7	8	9	10
i = 0	0	0	0	0	0	0	0	0	0	0	0
i = 1 ( 6, 13 )	0	0	0	0	0	0	13	13	13	13	13
i = 2 ( 4, 8 )	0	0	0	0	8	8	13	13	13	13	21
i = 3 ( 3, 6 )	0	0	0	6	8	8	13	14	14	19	21
i = 4 ( 5, 12 )	0	0	0	6	8	12	13	14	18	20	21

 

만약 

	0	1	2	3	4	5	6	7	8	9	10
i = 0	0	0	0	0	0	0	0	0	0	0	0
i = 1( 6, 13 )	0	0	0	0	0	0	13	13	13	13	13
i = 2 ( 4,  8 )	0	0	0	0	8	8	13	13	13	13	21

물건 1 = (무게 : 6, 가치 : 13)

물건 2 = (무게 : 4, 가치 :  8 )

물건 2개로 짐을 싸는 방법에서 

 

무게가 8일 때 현재 추가된 물건 2인 4키로를 담으면 8 - 4 = 4키로만큼 더 담을 수 있다.

이전 행의 4키로가의 가치가  0 이므로 가치는  8  +  0  = 8 (물건 2를 담은 가치)

하지만 해당 행의 4키로의 가치는 8이므로   8  +  8  = 16 (물건 2를 2개 담은 가치)

물건 2개를 담을 수 없음 그러므로 남은 무게는 이전 행의 가치로 계산한다.

 

 

import java.util.*;
public class Main {
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        int[][] dp = new int[N+1][K+1];
        int[] w = new int[N+1];
        int[] v = new int[N+1];

        for (int i = 1; i <= N; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= K; j++) {
                dp[i][j] = dp[i-1][j];
                if (j - w[i] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-w[i]] + v[i]);
                }
            }
        }
        System.out.println(dp[N][K]);
    }
}