Skip to content
Onsite
8 / 48

0-1 Knapsack

MediumP1Coding

You have n items, where item i has weight weights[i] and value values[i], and a bag that holds total weight at most capacity. Each item can be taken at most once (0-1 choice). Return the maximum total value you can carry.

Example 1

Input
weights = [1,3,4,5], values = [1,4,5,7], capacity = 7
Output
9
Why
Take the items with weights 3 and 4 for a value of 4 + 5 = 9.

Example 2

Input
weights = [10,20,30], values = [60,100,120], capacity = 50
Output
220

Example 3

Input
weights = [5], values = [10], capacity = 4
Output
0

Constraints

  • 1 <= n <= 100
  • 1 <= weights[i] <= 1000
  • 0 <= values[i] <= 10^4
  • 0 <= capacity <= 1000

Hints

Run checks the 3 visible tests, Submit all 11.