Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Recursive solution in Clear category for Knapsack Problem by amandel
from collections import namedtuple
it=namedtuple('it', 'v w m', defaults=(0,))
def knapsack(weight: int, items: list[tuple[int, int] | tuple[int, int, int]]) -> int:
if not items:
return 0
last=it(*items.pop())
return max(i*last.v+knapsack(weight-i*last.w,items[:])
for i in range(1+min(last.m or weight,weight//last.w)))
print("Example:")
print(knapsack(8, [(4, 3, 2), (2, 1, 1), (1, 2, 4), (3, 2, 2)]))
# These "asserts" are used for self-checking
assert knapsack(5, [(4, 2, 1), (5, 2, 1), (2, 1, 1), (8, 3, 1)]) == 13
assert knapsack(8, [(4, 2), (5, 2), (2, 1), (8, 3)]) == 21
assert knapsack(8, [(10, 10, 3)]) == 0
assert knapsack(8, [(4, 3, 2), (2, 1, 1), (1, 2, 4), (3, 2, 2)]) == 12
print("The mission is done! Click 'Check Solution' to earn rewards!")
May 23, 2023
