backpack

import java.util.stream.Collectors

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

def getKey(Integer i, Integer w) {
    return Arrays.asList(i, w)
}

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 ans(Integer i, Integer w, List<Integer> input, Map<List<Integer>, Integer> memo, List<Integer> output) {
    if (i == -1) {
        return
    }

    if (memo.get(getKey(i, w)) == memo.get(getKey(i - 1, w))) {
        ans(i - 1, w, input, memo, output)
    } else {
        output.push(input.get(i))
        ans(i - 1, w - input.get(i), input, memo, output)
    }
}

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() - 1, ref, input, memo)

def result = new ArrayList<Integer>()
ans(input.size() - 1, ref, input, memo, result)
println "anwser: $result"