Knapsack

knapsack.py

def value_of(knapsack, configuration):
    values = zip(knapsack, configuration)
    return sum(value for value, stolen in values
               if stolen is True)


def combinations_of(length):
    lst = [False] * length
    for i in range(2 ** length):
        for j in range(len(lst)):
            bit_set = i & (1 << j)
            if bit_set != 0:
                lst[j] = True
            else:
                lst[j] = False

        yield lst


def solve_knapsack(knapsack, limit):

    optimal_solution = [False] * len(knapsack)
    optimal_value = 0

    for configuration in combinations_of(len(knapsack)):
        config_value = value_of(knapsack, configuration)
        valuable = config_value > optimal_value
        valid = config_value <= limit

        if valid and valuable:
            optimal_solution = configuration[:]
            optimal_value = config_value

    return optimal_solution