Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
recursion solution in Clear category for Knapsack Problem by kdim
# https://www.geeksforgeeks.org/0-1-knapsack-problem-dp-10/
from functools import lru_cache
def knapsack(weight: int, items: list[tuple[int, int] | tuple[int, int, int]]) -> int:
items = [[v, w] for v, w, *n in items for _ in range(n.pop() if n else weight // w)]
@lru_cache()
def knp(w, n):
if w == 0 or n < 0:
return 0
if items[n][1] > w:
return knp(w, n - 1)
else:
return max(items[n][0] + knp(w - items[n][1], n - 1), knp(w, n - 1))
return knp(weight, len(items) - 1)
May 8, 2023
Comments:
