dynamic.py

# TABLE je ve skutečnosti instanční proměnná, ale berte to, jakože je globální

def solve():
    TABLE = {}  # slovník/hash kde klíče budou dvojice
    for cost in MAX_COST..0:
        weight, combo = _solve(NUMITEMS, cost)
        if weight <= CAPACITY:
            maxcombo = combo
            maxcost = cost
            return maxcombo, maxcost

def _solve(index, cost):
    if index == 0:
        if cost == 0:
            return 0, [False] * NUMITEMS
        return float('inf'), [True] * NUMITEMS  # whatever, tudy IMHO nikdy nepůjdem
    try:
        return TABLE[(index, cost)]
    except KeyError:
        index -= 1
        lesscost = cost - ITEMS[index]['cost']
        addweight = ITEMS[index]['weight']

        skip, skipstate = _solve(index, cost)
        add, addstate = _solve(index, lesscost)

        if skip < add + addweight:
            TABLE[(index + 1, cost)] = skip, skipstate.copy()
        else
            addstate = addstate.copy()
            addstate[index] = True
            TABLE[(index + 1, cost)] = add + addweight, addstate
        return TABLE[(index + 1, cost)]