import java.util.stream.Collectors

def memo = new HashMap<List<Integer>, Integer>()
def N = 20
def input = new IntRange(false, 0, N).collect { (Math.random() * 1000).intValue() }
println input

Integer m(Integer i, Integer w, List<Integer> input, Map<List<Integer>, Integer> memo) {
    def key = Arrays.asList(i, w)
    if (memo.containsKey(key)) {
        return memo.get(key)
    }

    if (i == -1) {
        return 0
    }

    if (input.get(i) > w) {
        def value = m(i - 1, w, input, memo)
        memo.put(key, value)
        return value
    }

    def value = Math.max(
            m(i - 1, w, input, memo),
            m(i - 1, w - input.get(i), input, memo) + input.get(i)
    )
    memo.put(key, value)
    return value
}

def average = input.stream().collect(Collectors.averagingInt { it }).intValue()
def ref = (average * N * 3 / 4).intValue()
println average
println "ref: $ref"
println m(input.size() - 2, ref, input, memo)