Given a knapsack capacity and a set of items, each with a weight and a value, return
the maximum total value you can carry without exceeding the capacity. Each item may be
taken at most once (0/1 knapsack).
knapsack(capacity, weights, values)
Input format: capacity | items, where items are weight,value pairs separated by
spaces.
capacity=10, items (5,10)(4,40)(6,30)(3,50) // → 90 (items of weight 4 and 3)
capacity=0, items (1,5) // → 0
For every item, a binary choice: take it or leave it. With n items, 2ⁿ combinations if tried directly — too slow beyond small inputs. Is there overlapping structure to exploit?
Working through items one at a time, deciding take-or-skip while tracking remaining capacity, the only things that matter for the rest of the decisions are: which items remain, and how much capacity is left. Which specific items were already taken doesn't matter beyond the capacity and value they consumed — two different already-decided subsets landing at the same (index, remaining capacity) are in an identical position going forward.
Define the subproblem as "best value achievable from index i onward with cap remaining." Only (items) × (capacity + 1) distinct pairs exist — far smaller than 2ⁿ.
At item i with capacity cap, two options:
The answer is the better of the two. Base case: no items left, value zero.
Evaluated naively, the same (i, cap) pair gets recomputed repeatedly through different take/skip sequences — overlapping subproblem structure, exactly what DP exploits. Caching the first computation of each pair collapses exponential work down to work proportional to the number of distinct pairs.
O(n · capacity) distinct subproblems, each O(1) work beyond its recursive calls thanks to memoization — O(n · capacity) total, a huge improvement over 2ⁿ brute force. "Decide item by item, track remaining capacity" is the standard framing for any 0/1 knapsack-shaped problem.
def knapsack(capacity, weights, values):
memo = {}
def best(i, cap):
if i == len(weights):
return 0
key = (i, cap)
if key in memo:
return memo[key]
res = best(i + 1, cap)
if weights[i] <= cap:
take = values[i] + best(i + 1, cap - weights[i])
if take > res:
res = take
memo[key] = res
return res
return best(0, capacity)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.