ARC 73 D - Simple Knapsack

D - Simple Knapsack
1≦N≦100
1 W 10^9
1 wi 10^9
w <= wi <= wi + 3
1 vi 10^7

与えられる重さが4種類しかないナップザック
[i個目を選ぶ時][選んだ個数][端数の合計を足した]の3次元で解いてみた

問題の芯
範囲が広くても、複数のまとまりになっていると分かる場合は、調べる範囲をかなり減らせる

public static void main(String[] args)
    {
        N = sc.nextInt();
        W = sc.nextInt();
        w = new int[N];
        v = new int[N];
        sc.nextIntArrays2ar(w, v);
        //i個目 選んだ数 あまりの合計
        long[][][] dp = new long[N + 1][N + 1][N * 3 + 1];
        for (int i = 0; i < N + 1; i++)
            fill(dp[i], -1);
        dp[0][0][0] = 0;
        long maxValue = 0;

        for (int i = 0; i < N; i++)
        {
            for (int c = 0; c < N; c++)
            {
                int rem = w[i] - w[0];
                for (int ri = 0; ri < N * 3 + 1; ri++)
                {
                    if (dp[i][c][ri] == -1) continue;
                    dp[i + 1][c][ri] = Math.max(dp[i][c][ri], dp[i + 1][c][ri]);
                    long nweidht = c * w[0] + ri + w[i];
                    if(nweidht > W)continue;
                    dp[i + 1][c + 1][ri + rem] = Math.max(dp[i + 1][c + 1][ri + rem], dp[i][c][ri] + v[i]);
                    maxValue = Math.max(maxValue, dp[i + 1][c + 1][ri + rem]);
                }
            }
        }
        System.out.println(maxValue);
    }