knapsack.knapsack

A recursive implementation of 0-N Knapsack Problem https://en.wikipedia.org/wiki/Knapsack_problem

Functions

knapsack(→ int)

Returns the maximum value that can be put in a knapsack of a capacity cap,

Module Contents

knapsack.knapsack.knapsack(capacity: int, weights: list[int], values: list[int], counter: int, allow_repetition=False) → int

Returns the maximum value that can be put in a knapsack of a capacity cap, whereby each weight w has a specific value val with option to allow repetitive selection of items

>>> cap = 50
>>> val = [60, 100, 120]
>>> w = [10, 20, 30]
>>> c = len(val)
>>> knapsack(cap, w, val, c)
220

Given the repetition is NOT allowed, the result is 220 cause the values of 100 and 120 got the weight of 50 which is the limit of the capacity. >>> knapsack(cap, w, val, c, True) 300

Given the repetition is allowed, the result is 300 cause the values of 60*5 (pick 5 times) got the weight of 10*5 which is the limit of the capacity.