BOJ. Knapsack problem (1450)

Problem: BOJ 1450 — Knapsack Problem

Meet in the middle

Enumerating all subsets of N = 30 items takes O(2^N) time. Instead, split the items into two halves and enumerate each half’s subset sums. Each list has at most 2^(N/2) sums. Sort the right-half sums; for every left-half sum s, binary-search for the first right-half sum greater than C - s. The number of sums before that position is exactly the number of right-half choices that fit with s.

Both enumerations start with the empty subset sum 0, so the empty subset is counted exactly once. Do not discard zero sums: every distinct subset is a choice, even if its sum is zero. All item weights are positive, so a half-sum greater than C can never be part of a valid combination; the implementation omits only those sums. Sums and the answer use long, because the answer can reach 2^30.

The time complexity is O(2^(N/2) log 2^(N/2)) and the space complexity is O(2^(N/2)).

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        long capacity = input.nextLong();
        int middle = n / 2;

        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = input.nextInt();
        }

        List<Long> leftSums = subsetSums(weights, 0, middle, capacity);
        List<Long> rightSums = subsetSums(weights, middle, n, capacity);
        Collections.sort(rightSums);

        long count = 0;
        for (long leftSum : leftSums) {
            count += upperBound(rightSums, capacity - leftSum);
        }

        System.out.println(count);
    }

    private static List<Long> subsetSums(int[] weights, int from, int to, long capacity) {
        List<Long> sums = new ArrayList<>();
        sums.add(0L);
        for (int i = from; i < to; i++) {
            int currentSize = sums.size();
            for (int j = 0; j < currentSize; j++) {
                long nextSum = sums.get(j) + weights[i];
                if (nextSum <= capacity) {
                    sums.add(nextSum);
                }
            }
        }
        return sums;
    }

    private static int upperBound(List<Long> sorted, long value) {
        int low = 0;
        int high = sorted.size();
        while (low < high) {
            int middle = low + (high - low) / 2;
            if (sorted.get(middle) <= value) {
                low = middle + 1;
            } else {
                high = middle;
            }
        }
        return low;
    }

    private static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = input.read();
            } while (c <= ' ' && c != -1);

            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = input.read();
            }
            return value;
        }
    }
}