Medium · Dynamic Programming

0/1 Knapsack

Given arrays weights and values describing n items and an integer capacity, return the maximum total value of a subset of the items whose total weight is at most capacity, using each item at most once.

Examples

Example 1

{
  "weights": [1, 3, 4, 5],
  "values": [1, 4, 5, 7],
  "capacity": 7
}

Output: value 9

Example 2

{
  "weights": [1, 2, 3],
  "values": [6, 10, 12],
  "capacity": 5
}

Output: value 22

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.