uber_knapsack.py

from decimal import Decimal as D


values = [
    '7.18', '7.13', '10.11', '7.67', '7.8', '6.77', '6.45', '6.57',
    '6.61', '7.86', '6.79', '6.76', '6.7', '7.72', '6.71', '7.45', '6.54',
    '6.75', '7.18', '6.77', '9.09', '26', '5.61', '7.41', '5.9', '9.35', '7.29',
    '6.25', '11.62', '7.34', '8.29', '6.95', '7.54', '8.36', '7.51', '6.2', '6.09',
    '7.3', '6.86', '6.67', '6.85', '6.17', '7.26', '5', '6.11', '6.07', '7.42',
    '7.87', '6.81', '6.66', '6', '6.58', '6.75', '7.67', '6.84', '6.76', '6.69',
    '6.98', '9.87', '6.82', '9.64', '7.37', '6.35', '6.15', '5.96', '7.82', '7.2',
    '7.94', '6.91', '6.68', '6.7', '6.14', '6.75', '7.48', '7.52',
]
values = [int(D(v) * 100) for v in values]
values = sorted(values, reverse=True)

goal_value = int(D('454.89') * 100)


counter = 0
def f(v, i, S, memo):
    global counter

    if S == 0:  # achamos
        return True

    if i >= len(v):  # ultimo item
        return False

    if v[i] > S:
        return False

    if (i, S) not in memo:  # <-- Check if value has not been calculated.
        counter += 1

        a = lambda: f(v, i + 1, S, memo)  # avança sem inserir
        b = lambda: f(v, i + 1, S - v[i], memo)  # avança inserindo

        memo[(i, S)] = b() or a()    # <-- Memoize calculated result.

    return memo[(i, S)]          # <-- Return memoized value.

def g(v, S, memo):
    subset = []
    for i, x in enumerate(v):
        # Check if there is still a solution if we include v[i]
        if f(v, i + 1, S - x, memo):
            subset.append(x)
            S -= x
    return subset

memo = {}
if f(values, 0, goal_value, memo) == 0:
    print("There are no valid subsets.")
else:
    answer = g(values, goal_value, memo)
    print(answer)
    print(sum(answer), goal_value)
    assert sum(answer) == goal_value
    print(counter)