12865 : 평범한 배낭 - Java

12865번: 평범한 배낭

대표적인 0 - 1 배낭 문제이다.

물건 N개와 배낭의 크기인 K가 주어지고 2번째 줄부터 물건의 가치와 무게가 주어진다.
이때 최대 가치를 구하는 문제다.

4 7
6 13
4 8
3 6
5 12

문제와 같이 예제가 주어졌을 경우 최대 담을 수 있는 물건은 4개 배낭의 최대 사이즈는 7이된다.
이에 맞는 배열을 준비하면 dp = new int[5][8]이 된다. 물건과 사이즈는 0이 될 수 없으므로 +1씩 해줬다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,0,0]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]

위와 같이 dp 배열이 초기화되어 있을 것이다. 여기서 열은 무게를 행은 물건의 개수를 나타낸다.

첫 번째, 물건을 확인해보자.
이 물건의 무게는 6이고, 가치는 13이다. 이 물건을 담기 위해서는 최소 6칸의 공간이 필요하다.
따라서 0 ~ 5의 공간에는 담을 수 없다. 6번 인덱스에 해당 물건을 담는다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,0]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]

위와 같이 6번 인덱스에 물건의 가치인 13을 담았다. 7번 인덱스 부터는 6번인덱스에서 물건을 담았기 때문에 해당 가치가 유지된다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,0,0,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]

두 번째 물건은 무게가 4이고 가치가 8이다. 4번인덱스 이전에는 해당 물건을 담을 수 없다. 4번 인덱스에는 물건을 넣을 수 있다. 또한 5번 인덱스 역시 가치가 유지된다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,0,0]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]

그러나 6번 인덱스 역시 물건을 담을 수 있다. 그러나 이전 물건을 담았을 때의 가치가 더 크다. 따라서, 이전 물건의 가치로 채워준다.
7번 역시 마찬가지다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,0,0,0,0,0]
dp[4] = [0,0,0,0,0,0,0,0]

세 번째 물건을 보면 무게는 3이고 가치는 6이다. 다시 채워보자.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,6,8,8,13,0]
dp[4] = [0,0,0,0,0,0,0,0]

4 ~ 6번까지는 무게가 더 큰 이전 인덱스의 값으로 채워줬다. 하지만 7번 인덱스의 경우에는 이전 물건까지 체크해봤을 때. 현재 무게를 뺀 가치 즉, dp[2][4](8) 에 현재 물건을 넣었을 때 증가하는 가치(+6), 14가 이전 물건까지 체크했을 때 7번 인덱스의 최댓값 13보다 크다. 따라서, 14를 채워준다.

dp[0] = [0,0,0,0,0,0,0,0]
dp[1] = [0,0,0,0,0,0,13,13]
dp[2] = [0,0,0,0,8,8,13,13]
dp[3] = [0,0,0,6,8,8,13,14]
dp[4] = [0,0,0,0,0,0,0,0]

그렇다면 아래와 같이 점화식을 세울 수 있다.

dp[현재 물건][현재 사이즈]에 대하여
    현재 물건의 사이즈보다 현재 체크하는 공간의 사이즈가 작다면?
        dp[현재 물건][현재 사이즈] = dp[이전 물건][현재 사이즈]
    크다면?
        dp[현재 물건][현재 사이즈] = max(dp[이전 물건][현재 사이즈], dp[이전 물건][현재 사이즈 - 현재 물건 사이즈])

물건의 무게를 w, 가치를 v라고 하면 이를 코드로 나타내면 다음과 같다.

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

전체 코드

import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int[][] dp;
    static int N, K;

    public static void main(String[] args) throws IOException {
//        System.setIn(Files.newInputStream(Paths.get("src/input.txt")));
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        dp = new int[N + 1][K + 1];

        for (int i = 1; i < N + 1; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken()), v = Integer.parseInt(st.nextToken());
            for (int j = 1; j < K + 1; j++) {
                if (j < w) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], v + dp[i - 1][j - w]);
                }
            }
        }
        bw.write(dp[N][K] + "");
        bw.flush();
        bw.close();
        br.close();
    }


}