Language: Java

package org.zlambda.sandbox.puzzle;

import java.util.*;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.Stream;
/**
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_H

??¨??§???????????¶????????????
????????? vi ????????? wi ??§??????????????? N ??????????????¨???????????? W ??????????????¶?????????????????????????¬?????????¶?????????????????????????????????????????§???????????¶???????????\????????????

???????????????????????????????¨??????§???????????????????????????
???????????????????????????????????? W ????¶?????????????
?????????????¨?????????§???????±??????????????????????

??\???
???????????????????????´??°???N???W???????????????????????§?????????????????????????????? ?¶???? N ?????§ i ???????????????????????? vi ??¨?????? wi ????????????????????§?????????????????????

??????
?????????????¨?????????§??????????????????????????????????????????

??¶?´?
1 ??? N ??? 40
1 ??? vi ??? 10^15
1 ??? wi ??? 10^15
1 ??? W ??? 10^15
??\?????????

??\?????? 1
4 5
4 2
5 2
2 1
8 3
????????? 1
13

??\?????? 2
2 20
5 9
4 10
????????? 2
9

 ?????????????????????
 1. ?????????????????????????????????????????????(v,w)
 2. for each pair (v1[i],w1[i]) in group one, we find max(v1[i] + v2[j]), for every j such that w2[j] <= W - w1[i]
 3. Sort (v2, w2) by w2. then we have
 3.1 w2[i] <= w2[j] for each i < j
 3.2 then we filter out all i such that w2[i] <= w2[j] and v2[i] < v2[j]
*/
public class Knapsack01Huge {
    public static class Solver {
        long solve(final long W, List<Long> values, List<Long> weights) {
            int N = values.size();
            int n1 = N >> 1;

            List<VW> gp1 = getVWs(getCombinations(0, n1), values, weights);
            gp1.add(new VW(0, 0));

            List<VW> gp2 = getVWs(getCombinations(n1, N), values, weights);
            gp2.add(new VW(0, 0));
            Collections.sort(gp2);

            List<VW> filteredGp2 = new ArrayList<>();
            VW prev = null;
            for (VW vw : gp2) {
                if (null == prev || prev.value < vw.value) {
                    prev = vw;
                    filteredGp2.add(prev);
                }
            }

            long ret = 0;
            for (VW p : gp1) {
                long w = Math.max(W - p.weight, 0);
                int idx = Collections.binarySearch(filteredGp2, new VW(-1, w), Comparator.comparingLong(pp -> pp.weight));
                long v = 0;
                if (idx >= 0) {
                    v = filteredGp2.get(idx).value;
                } else {
                    idx = -idx - 1;
                    idx = idx - 1;
                    if (idx >= 0) {
                        v = filteredGp2.get(idx).value;
                    }
                }
                ret = Math.max(ret, p.value + v);
            }
            return ret;
        }

        private static List<VW> getVWs(List<List<Integer>> combs, List<Long> values, List<Long> weights) {
            return combs.stream().map(
                    comb -> comb.stream()
                            .map(i -> new VW(values.get(i), weights.get(i)))
                            .reduce((res, vw) -> new VW(res.value + vw.value, res.weight + vw.weight))
                            .get()
            ).collect(Collectors.toList());
        }

        private static List<List<Integer>> getCombinations(int idx, int length) {
            List<Integer> comb = new ArrayList<>();
            List<List<Integer>> combs = new ArrayList<>();
            getCombinations(idx, length, comb, combs);
            return combs;
        }

        private static void getCombinations(int idx, int length, List<Integer> comb, List<List<Integer>> combs) {
            if (idx == length) {
                if (comb.size() != 0) {
                    combs.add(new ArrayList<>(comb));
                }
                return;
            }
            {
                comb.add(idx);
                getCombinations(idx + 1, length, comb, combs);
                comb.remove(comb.size() - 1);
            }
            {
                getCombinations(idx + 1, length, comb, combs);
            }
        }

        private static class VW implements Comparable<VW> {
            private final long value;
            private final long weight;
            private VW(long value, long weight) {
                this.value = value;
                this.weight = weight;
            }

            @Override
            public int compareTo(VW o) {
                return Long.compare(weight, o.weight);
            }

            @Override
            public String toString() {
                return String.format("[v:%d,w:%d]", value, weight);
            }
        }
    }

    private static final Pattern SPLIT = Pattern.compile("\\s");
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Long> weights = new ArrayList<>();
        List<Long> values = new ArrayList<>();
        List<Long> NW = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
                .collect(Collectors.toList());
        final long N = NW.get(0);
        final long W = NW.get(1);
        for (int i = 0; i < N; ++i) {
            List<Long> collect = Stream.of(SPLIT.split(scanner.nextLine())).map(Long::valueOf)
                    .collect(Collectors.toList());
            values.add(collect.get(0));
            weights.add(collect.get(1));
        }
        System.out.println(new Solver().solve(W, values, weights));
    }
}

Compiler output:
Main.java:53: error: class Knapsack01Huge is public, should be declared in a file named Knapsack01Huge.java
public class Knapsack01Huge {
       ^
1 error