E - Knapsack 2 / atcoder.jp

문제 링크 : https://atcoder.jp/contests/dp/tasks/dp_e
문제 해설 : https://jinpyo.kim/EducationalDP-solution
Submission : https://atcoder.jp/contests/dp/submissions/10059004
Java Source : https://github.com/skysign/WSAPT/blob/master/atcoder.jp/E%20-%20Knapsack%202/src/Main.java

이전 문제인 'D - Knapsack 1'의 풀이를 그대로 적용하면, Sample Input 1~3에서는 올바른 값이 나올 수도 있지만, 실제 이 문제는 약간 다른 방식으로 접근해야 합니다.

문제의 Constraints에서 알 수 있듯이, wi 값의 범위가 매우 크기 때문에, DP를 무게 W를 기준으로 배열을 만들면, 배열의 크기가 너무 커지고, 배열이 커진 만큼 속도도 느려짐니다.

그래서, 이번에는 조금 다른 방식으로 v를 기준으로 배열을 만들고, dp[i][j]의 값은 무게가 됩니다.
따라서, 무게 W 보다 작은 값중에 value의 합기 가장 큰 값을 리턴해줍니다.

\begin{aligned}
d_{ij} = min(d_{i-1,j-v_i} + w_i, d_{i-1,j}) \\
\end{aligned}

\begin{aligned}
V = \sum_{i=1}^N v_i
\end{aligned}
V는 모든 값의 합이 되고, DP를 계산하는 배열의 크기는 dp[N+1][V+1]이 됩니다.

public class Main {
    public static long Knapsack2(int N, int W, int[] ws, int[] vs) {
        // Java 8에서 새로 추가된 Stream을 사용해서, 합을 구해봅니다.
        int V = IntStream.of(vs).sum();
        OptionalInt W_MAX = IntStream.of(ws).max();

        // 문제의 'Constraints'에서 주어진것 처럼 Wi의 값이 매우 크기 때문에,
        // int를 사용해서 풀면, overflow 되는 문제가 발생합니다.
        long[][] dp = new long[N+1][V+1];

        for(int n=0; n<=N; ++n) {
            for(int v=0; v<=V; ++v) {
                // dp를 추후에 계산할 때, overflow가 되어서, - 값으로 바뀌는 것을 피하기 위해서
                // 모든 value의 합인 W_MAX 를 빼주게 됩니다.
                dp[n][v] = Long.MAX_VALUE - W_MAX.getAsInt();
            }
        }

        long value = 0;
        dp[0][0] = 0;
        for(int i=1; i<=N; ++i) {
            for(int v=0; v<=V; ++v) {
                dp[i][v] = Math.min(dp[i-1][v], dp[i][v]);
                if(v-vs[i]>=0)
                    dp[i][v] = Math.min(dp[i][v], dp[i-1][v-vs[i]] + ws[i]);
                if(dp[i][v] <= W) {
                    value = Math.max(value, v);
                }
            }
        }

        return value;
    }

    public static void main(String[] args) throws IOException {
//         Scanner sc = new Scanner(System.in);
        Reader sc = new Reader();
        int N = sc.nextInt();
        int W = sc.nextInt();
        int[] ws = new int[N+1];
        int[] vs = new int[N+1];
        PrintWriter pw = new PrintWriter(System.out);

        for(int i=1; i<=N; ++i) {
            ws[i] = sc.nextInt();
            vs[i] = sc.nextInt();
        }

        long r = Knapsack2(N, W, ws, vs);

        pw.println(r);
        pw.close();
    }
    ...
    // reader class는 github에 자바코드 참고하세요.
}