백준 - 12865 평범한 배낭(Java)

 

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

 

가장 유명하고 대표적인 DP 문제라 생각합니다.

 

물건의 개수 N과 N만큼 각 물건의 가중치가 주어집니다.

가방이 견딜 수 있는 최대 무게 K가 주어졌을 때, 가방에 넣을 수 있는 물건의 최대 가중치를 구하는 문제입니다.

 

이 문제를 해결하기 위해서는 물건과 무게에 따른 가중치를 저장할 2차원 배열이 필요합니다.

2차원 배열의 행은 물건의 개수만큼 필요하고, 열은 가방이 견딜 수 있는 최대 무게만큼 필요합니다.

즉 dp[N][K] 만큼 필요한 것입니다.

특정 i행 과 j열의 값은 i열 만큼 물건(i)을 넣었을 때 무게(j)의 최대 가중치인 것입니다.

 

문제에 주어지는 물건을 차례대로 가방에 넣을 때의 가중치를 무게에 따라 갱신을 하면 됩니다.

현재 물건을 넣지 못하는 경우 dp[i][j] = dp[i-1][j]가 됩니다.

현재 물건을 넣는 경우에는 dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)가 됩니다.

문제의 예시를 그림으로 표현하면 위와 같습니다.

i=3, j=7인 경우

j-w = 7-3 = 4이고, 현재 가중치(v)는 6이므로

dp[3][7] = max(dp[3][7], dp[3][4] + 6) = 14가 됩니다.

 

결국 dp[4][7]는 14가 됩니다.

 

[구현 코드]

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

public class Main {
    private static int n, k;
    private static int[][] stuff, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine(), " ");
        n = Integer.parseInt(stz.nextToken());
        k = Integer.parseInt(stz.nextToken());

        stuff = new int[n + 1][2];
        dp = new int[n + 1][k + 1];

        for (int i = 1; i < n + 1; i++) {
            stz = new StringTokenizer(br.readLine(), " ");
            stuff[i][0] = Integer.parseInt(stz.nextToken()); // 무게
            stuff[i][1] = Integer.parseInt(stz.nextToken()); // 가치
        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 1; j < k + 1; j++) {
                int w = stuff[i][0]; // 현재 물건 무게
                int v = stuff[i][1]; // 현재 물건 가치

                // 견딜 수 있는 총 무게에서 현재 물건의 무게를 버틸 수 있는 경우
                if (j - w >= 0) {
                    // 물건을 넣는 경우의 가중치와 물건을 넣기 이전의 가중치를 비교하여 큰 값으로 갱신
                    // j - w 의미는 이전에 넣은 물건들과 현재 물건을 같이 넣을 수 있는 경우임
                    dp[i][j] = Math.max(dp[i - 1][j],
                            dp[i - 1][j - w] + v);
                } else {
                    // 견딜 수 없는 경우
                    // 이전 가방 무게의 총 가중치를 그대로 가져옴
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        bw.write(String.valueOf(dp[n][k]));

        bw.flush();
        bw.close();
        br.close();

    }
}