FastPrep
Problem · Dynamic Programming

0/1 Knapsack

Learn this problem
● MediumMicrosoft logoMicrosoftFULLTIMEOA
See Microsoft hiring insights

Problem statement

You are given two arrays, weights and values, describing n items. Item i has weight weights[i] and value values[i].

Choose a subset of the items whose total weight is at most capacity. Each item may be chosen at most once. Return the maximum total value achievable.

Function

maximumKnapsackValue(weights: int[], values: int[], capacity: int) → int

Examples

Example 1

weights = [1,3,4,5]values = [1,4,5,7]capacity = 7return = 9

Choosing the items with weights 3 and 4 uses the full capacity and yields value 4 + 5 = 9.

Example 2

weights = [2,2,3]values = [6,10,12]capacity = 5return = 22

The second and third items fit together and yield value 22.

Example 3

weights = [4,5]values = [8,9]capacity = 3return = 0

No item fits, so the empty subset is optimal.

Constraints

  • 0 <= weights.length = values.length <= 200
  • 1 <= weights[i] <= 10000
  • 0 <= values[i] <= 1000000
  • 0 <= capacity <= 10000
  • The maximum answer fits in a signed 32-bit integer.

More Microsoft problems

drafts saved locally
public int maximumKnapsackValue(int[] weights, int[] values, int capacity) {
    // Write your solution here
}
weights[1,3,4,5]
values[1,4,5,7]
capacity7
expected9
checking account