Submission #5553897

---

Source Code Expand

import java.util.*;

public class Main {
    private static final long INF = 200 * 1000000000L + 1;

    int n, lw;
    long v[], w[];

    public void main(Scanner sc) {
        n = sc.nextInt();
        lw = sc.nextInt();
        v = new long[n];
        w = new long[n];

        for (int i = 0; i < n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        long maxValue = Arrays.stream(v).max().getAsLong();
        long maxWeight = Arrays.stream(w).max().getAsLong();
        if (maxValue <= 1000) {
            System.out.println(knap1((int) maxValue));
        } else if (maxWeight <= 1000) {
            System.out.println(knap2());
        } else {
            System.out.println(knap3());
        }
    }

    private long knap1(int mv) {
        long dp[] = new long[n * mv + 1];
        Arrays.fill(dp, INF);

        dp[0] = 0;
        for (int i = 0; i < n; i++) {
            int vi = (int) v[i];
            for (int j = n * mv; j >= vi; j--) {
                dp[j] = Math.min(dp[j], dp[j - vi] + w[i]);
            }
        }

        long ans = 0;
        for (int i = 0; i <= n * mv; i++) {
            if (dp[i] <= lw) {
                ans = i;
            }
        }

        return ans;
    }

    private long knap2() {
        long dp[][] = new long[n + 1][lw + 1];

        for (int i = 1; i <= n; i++) {
            int wi = (int) w[i - 1];
            for (int j = wi; j <= lw; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wi] + v[i - 1]);
            }
        }

        return dp[n][lw];
    }

    private long knap3() {
        int n1 = n / 2;
        int n2 = n - n1;

        Map<Long, Long> wv1 = new TreeMap<>((v1, v2) -> Long.compare(v1, v2));
        Map<Long, Long> wv2 = new TreeMap<>((v1, v2) -> Long.compare(v1, v2));

        for (int i = 0; i < (1 << n1); i++) {
            long sumW = 0, sumV = 0;
            for (int j = 0; j < n1; j++) {
                if ((i >> j) % 2 == 1) {
                    sumW += w[j];
                    sumV += v[j];
                }
            }
            wv1.put(sumV, Math.max(wv1.getOrDefault(sumV, 0L), sumW));
        }

        for (int i = 0; i < (1 << n2); i++) {
            long sumW = 0, sumV = 0;
            for (int j = 0; j < n2; j++) {
                if ((i >> j) % 2 == 1) {
                    sumW += w[j + n1];
                    sumV += v[j + n1];
                }
            }
            wv2.put(sumV, Math.max(wv2.getOrDefault(sumV, 0L), sumW));
        }

        long ans = 0;
        for (Map.Entry<Long, Long> entry1 : wv1.entrySet()) {
            long nw1 = entry1.getValue();
            long nv1 = entry1.getKey();
            if (nw1 > lw) {
                continue;
            }

            for (Map.Entry<Long, Long> entry2 : wv2.entrySet()) {
                long nw2 = entry2.getValue();
                if (nw1 + nw2 > lw) {
                    continue;
                }

                ans = Math.max(ans, nv1 + entry2.getKey());
            }
        }

        return ans;
    }

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            new Main().main(sc);
        } catch (Exception e) {
            throw e;
        }
    }
}

Submission Info

Judge Result