Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
First solution in Clear category for Knapsack Problem by imloafer
def knapsack(weight: int, items: list[tuple[int, int] | tuple[int, int, int]]) -> int:
# your code here
items = [(v, w) for v, w, *m in items for _ in range((m[0] if m else weight // w))]
dp = [0] * (weight + 1)
for v, w in items:
for j in range(weight, w-1, -1):
dp[j] = max(dp[j], v + dp[j-w])
return dp[weight]
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!")
April 19, 2023