백준 12865 평범한 배낭 Java

대표적인 dp문제 중 하나인 냅색 문제이다.

 

냅색 문제는 무게 K가 주어졌을 때

무게에 맞게 물건들을 최대 가치로 넣는 문제이다.

 

다른 냅색 문제들은 모르겠지만

이 문제는 한 번 넣은 물건은 또 못 넣는다는 점에 주의해야 한다.

 

dp배열을

2차원 배열로 사용하는 방법과

1차원 배열로 사용하는 방법이 있다.

 

2차원 배열은

dp[i][j] = 무게가 i일 때 j번째 물건까지 넣었을 때의 최대 가치이다.

 

이를 통해 점화식을 짜면

if(i >= w[j]) {
   dp[i][j] = Math.max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]); 
} else {
    dp[i][j] = dp[i][j-1];
}

 이렇게 점화식이 나올 수 있다.

여기서 dp[i-w[j]] [j-1] + v[j] 를 보면

앞에서 구한 dp배열 중 무게가 i일때 j번째 물건의 무게를 뺀

가방에 남는 공간에 넣을 수 있는 최대의 가치와 현재 물건의 가치를 더한다. 

dp[i-w[j]] [j] + v[j] 로 처음엔 구했었는데

 4 6
 6 13
 3 8
 7 15
 2 6

이렇게 입력이 주어지면

크기가 6일 때 2번째 물건의 가치인

8을 더하고 i-w[j] = 3

크기가 3일 때 2번째 물건의 가치를 또 더하게 돼서

결국 2번째 물건의 가치를 2번 더하게 된다.

문제에서는 물건을 한개씩만 가방에 넣을 수 있으므로

같은 물건을 제외한 가장 최대가치인 dp[i-w[j]] [j-1]을 사용해서

dp[i-w[j]] [j-1] + v[j] 로 점화식을 짜야한다.

 

예제로 주어진 

4 7

6 13

4 8

3 6

5 12

으로 점화식대로 dp표를 채워보면

k/n	1	2	3	4
1	0	0	0	0
2	0	0	0	0
3	0	0	6	6
4	0	8	8	8
5	0	8	8	12
6	13	13	13	13
7	13	8	14	14

직접 표를 그려보면 이해하기 쉽다.

 

1차원 배열의 경우에는 

dp[i] = 무게가 i일 때 최대 가치이다.

 

1차원 dp배열이라고해서 for문을 한 번만 쓰고

문제를 해결하는 것은 불가능하다.

2차원과 똑같이 for문을 2번돌리지만

실행 속도는 2차원보다 훨씬 빠르다.

 

점화식도 2차원 때와 비슷하다.

dp[j]=Math.max(dp[j],dp[j-w[i]]+value[i]);

다만 for문이 다르다.

for(int i=1; i<=n; i++) {
    for(int j=k; j-w[i]>=0;j--) {
        dp[j]=Math.max(dp[j],dp[j-w[i]]+value[i]);
    }
}

i번째 물건을 기준으로

j를 k값으로 두고 j-w[i]가 가능하면 계속해서 j를 -1해주면서

최대 값을 찾는다.

 

예제로 주어진 입력이 for문에 따라 dp배열이 바뀌는 과정을 보면

4 7

6 13

4 8

3 6

5 12

 

i = 1 j = 7
[0, 0, 0, 0, 0, 0, 0, 13]
i = 1 j = 6
[0, 0, 0, 0, 0, 0, 13, 13]
i = 2 j = 7
[0, 0, 0, 0, 0, 0, 13, 13]
i = 2 j = 6
[0, 0, 0, 0, 0, 0, 13, 13]
i = 2 j = 5
[0, 0, 0, 0, 0, 8, 13, 13]
i = 2 j = 4
[0, 0, 0, 0, 8, 8, 13, 13]
i = 3 j = 7
[0, 0, 0, 0, 8, 8, 13, 14]
i = 3 j = 6
[0, 0, 0, 0, 8, 8, 13, 14]
i = 3 j = 5
[0, 0, 0, 0, 8, 8, 13, 14]
i = 3 j = 4
[0, 0, 0, 0, 8, 8, 13, 14]
i = 3 j = 3
[0, 0, 0, 6, 8, 8, 13, 14]
i = 4 j = 7
[0, 0, 0, 6, 8, 8, 13, 14]
i = 4 j = 6
[0, 0, 0, 6, 8, 8, 13, 14]
i = 4 j = 5
[0, 0, 0, 6, 8, 12, 13, 14]

 

이런식으로 바뀌는 걸 볼 수 있다.

dp는 정말 어려운 것 같다.

 

2차원 dp 배열

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q12865 {
 
    public static void main(String[] args) throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[k+1][n+1]; //가방의 크기가 i일때 j번째 물건까지 담을 경우 최대가치
        int [] w = new int[n+1];
        int [] v = new int[n+1];
 
        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(reader.readLine());
            w[i] = Integer.parseInt(st.nextToken());
            v[i] = Integer.parseInt(st.nextToken());
        }
 
        for(int i=1; i<=k; i++) {
            for(int j=1; j<=n; j++) {
                if(i >= w[j]) {
                    //남는 무게의 가치를 추가할 때 같은 물건을 추가하면 안되므로 j-1
                    //같은 물건을 제외하고 가치가 높을 때가 j-1이다.
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-w[j]][j-1]+v[j]); 
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        System.out.println(dp[k][n]);
    }
}

 

1차원 dp 배열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q12865_ver2 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] input = in.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]); 
 
        int[] w = new int[n+1]; //무게
        int[] value = new int[n+1]; //가치
        int[] dp = new int[k+1];
 
        for(int i=1; i<=n; i++) {
            input = in.readLine().split(" ");
            w[i] = Integer.parseInt(input[0]);
            value[i] = Integer.parseInt(input[1]);
        }
 
 
        for(int i=1; i<=n; i++) {
            for(int j=k; j-w[i]>=0;j--) {
                dp[j]=Math.max(dp[j],dp[j-w[i]]+value[i]);
            }
        }
        System.out.println(dp[k]);
    }
}