knapsack problem

Item has value and weight. Maximize value for given items and max weight.

item:
    value
    weight

// O(2^n) time
knapsack(items, maxweight):
    maxway = new way()
    maxcombine(items, maxweight, maxway, new way(), start: 0)
    return maxway

maxcombine(items, maxweight, maxway, way, start):
    if start > 0:
        if way.weight > maxweight:
            return
        if way.value > maxway.value:
            maxway.clear()
            maxway.add(item for item in way)
    if start == items.length():
        return
    for i = start, i < items.length(), i++:
        way.add(items[i])
        combine(items, maxweight, maxway, way, i+1)
        way.removelast()

way:
    weight = 0
    value = 0
    list items = new
    value:
        return value
    weight:
        return weight
    add(item):
        items.add(item)
        weight += item.weight
        value += item.value
    removelast():
        item = items.removelast()
        weight -= item.weight
        value -= item.value