[Beakjoon] 12865 평범한 배낭 (Java++)

문제 링크

BOJ 12865 : 평범한 배낭

문제

N개의 물건과 배낭이 수용 가능한 최대 무게 K가 주어진다.
물건은 각각 무게 w와 가치 v값을 가진다.
배낭에 담을 수 있는 물건 가치의 최대값을 구하는 문제이다.

풀이

어떤 물건을 담아야 최대 가치를 가질지 예상이 불가능하다.
탐욕법처럼 특정 물건을 보고 해당 물건을 담을지 담지 말지 결정하는 것이 불가능하다는 의미이다.

따라서 다이나믹프로그래밍 알고리즘을 사용한다.

2차원 배열 활용

dp[i][j]에서 저장된 값이 의미하는 바는 i번째 물건까지 봤을 때 무게j를 만드는 최대 물건 가치이다.

점화식은 다음과 같다.

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

즉 i번째 물건을 담지 않았을 때 무게가 j-w인 상태에서 i번째 물건을 담는 경우 vs 현재 dp[i-1][j]에 저장된 값(i번째 물건을 사용하지 않는 경우) 을 비교하여 더 큰 값을 저장한다.

1차원 배열을 활용해
dp[i]를 무게 i를 만드는 최대 가치라고 풀게 되면 물건을 중복해서 담는 경우가 생긴다.
ex) item1의 값이 w = 2, v= 100이라고 했을 때 K=4인 상황
dp[2] = 100;
dp[4] = 200;
-> item1이 두번 담아진다.

따라서 배열을 2차원으로 분리해서 i번째 물건은 한 번만 담기도록 하였다.

1차원 배열 활용

업데이트를 거꾸로 하면 물건을 중복해서 담는 경우가 발생하지 않는다.

		for(int j=K; j>=w; j--) {
            dp[j] = Math.max(dp[j], dp[j-w]+v);
        }

코드

public class Main {
    private static int N, K;

    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());

        int answer = 0;
        int w, v;
        int[][] dp = new int[N+1][K+1];
        /*
        dp[i][j] 의 의미
        i번째 물건을 사용해서 무게 j를 만들 때 최대 가치
         */
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            w = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            for(int j = 0; j <= K; j++) {
                if(j<w) {
                    dp[i][j] = dp[i - 1][j];
                    continue;
                }
                dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-w] + v);
                answer = Math.max(answer, dp[i][j]);
            }
        }

        System.out.println(answer);
    }
}