noodleProblems/
0/1 Knapsack
#157

0/1 Knapsack

AlgorithmmediumArrayDynamic Programming

You're packing a knapsack that can carry a total weight of cap. There are n candidate items, where item i weighs weights[i] and is worth values[i].

Choose a subset of the items so the combined weight is at most cap and the combined value is as large as possible. Each item may be used **at most once** — you either pack it whole or leave it behind, there's no taking a fraction of an item and no taking the same item twice.

Return the maximum total value achievable.

Example cases

  • three items pack the knapsack exactly
    in cap = 10, weights = [1,3,4,5], values = [1,4,5,7]
    out 13
    Take the items weighing 1, 4, and 5 (total weight 10, right at capacity) for value 1 + 5 + 7 = 13 — no other subset beats it.
  • zero capacity
    in cap = 0, weights = [1,2,3], values = [10,20,30]
    out 0
    A capacity of 0 rules out every item, so nothing can be packed.
  • single item exactly fits
    in cap = 5, weights = [5], values = [100]
    out 100
  • every item fits at once
    in cap = 6, weights = [1,2,3], values = [6,10,12]
    out 28
    The items' weights sum to exactly 6, so all three fit: 6 + 10 + 12 = 28.

Constraints

  • 0 <= cap <= 10^4
  • 0 <= weights.length == values.length <= 200
  • 1 <= weights[i] <= 10^4
  • 1 <= values[i] <= 10^4
Saved
cap =
10
weights =
[1,3,4,5]
values =
[1,4,5,7]