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

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

12865번: 평범한 배낭

문제 풀이

당연히 완전탐새은 시간초과나는 dp 문제이다. 먼저 1~k까지의 무게에 최대 가치를 저장하기 위한 dp가 필요하다. 여기서 item들이 여러 조합으로 선택될 수 있으니 각 아이템에 대한 정보도 필요하므로 2차원 배열로 선언해야 한다는 것을 파악해야 한다.

 

먼저 경우의 수가 2가지 나온다.

1.  1~k까지 반복하며 해당 무게로 현재 진행 중인 아이템을 담을 수 없는 경우 -> 같은 무게의 이전 아이템에 대한 값과 동일하게 내려옴 
2.  해당 무게로 현재 진행 중인 아이템도 담고, 남은 무게로 더 담을 수 있는 경우
   • dp[item][weight] = Math.max(dp[item - 1][weight], dp[item - 1][weight - w[item]] + v[item])
   • 7 무게 중 4를 쓰고 남은 무게 3중 최대치는 dp[x][3]에 있을 것이다. 이 값은 현재 아이템 이전에 나온 값들이므로 dp[x-1][3]이고 이 식을 위와 같이 표현할 수 있다.

이렇게 각 경우룰 구분하여 문제를 해결할 수 있다.

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class b12865 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        int[][] dp = new int[n + 1][k + 1]; // row 아이템으로 col 무게에 담을 수 있는 최대치
        int[] w = new int[n + 1]; // 무게
        int[] v = new int[n + 1]; // 가치

        for (int item = 1; item <= n; item++) {
            st = new StringTokenizer(br.readLine());
            w[item] = Integer.parseInt(st.nextToken());
            v[item] = Integer.parseInt(st.nextToken());

            for (int weight = 1; weight <= k; weight++) {
                //현재 아이템의 무게가 현재 수용할 수 있는 무게 j보다 큰 경우, 이전 상단값으로 값지정
                if (w[item] > weight)
                    dp[item][weight] = dp[item - 1][weight];

                    // (현재 아이템의 무게를 수용 + 남은 무게로 넣을 수 있는 최대치)와 이전 상단값과 비교
                else
                    dp[item][weight] = Math.max(dp[item - 1][weight], dp[item - 1][weight - w[item]] + v[item]);
            }
        }

        System.out.println(dp[n][k]);
    }
}

 

느낀점

예전에 한 번 풀어봤던 문제로 다시 풀어봤는데 역시나 어렵다. 완전탐색으로는 풀 수 있겠는데 dp로 하려니 값을 어떻게 나누고 어떤 값을 보관해야할지 감이 안잡혔다