Suppose you have a list of weights and corresponding values for n items. You have a knapsack that can carry items up to a specific maximum weight, known as the capacity of the knapsack.

You want to maximize the sum of values of the items in your knapsack while ensuring that the sum of the weights of the items remains less than or equal to the knapsack’s capacity.

If all the combinations exceed the given knapsack’s capacity, then return 00.

Note: While adding items in the knapsack, we either add the complete item or don’t add it. Moreover, we can’t add an item again that is already in the bag.

Let’s say you have a knapsack capacity of 5 and a list of items with weights and values as follows:

weights = [1, 2, 3, 5]

values = [10, 5, 4, 8]

There are four ways of storing items in the knapsack, such that the combined weight of stored items is less than or equal to the knapsack’s capacity.

  • Item of weight 1 and weight 2, with a total value of 15.
  • Item of weight 1 and weight 3, with a total value of 14.
  • Item of weight 2 and weight 3, with a total value of 9.
  • Item of weight 5, with a value of 8.

Though all of the combinations described above are valid, we need to select the one with the maximum value. Hence, we will select items with weights 1 and 2, as they give us the maximum value of 15.


  • 11 \leq capacity 104\leq 10^4
  • 11 \leq values.length 103\leq 10^3
  • weights.length ==== values.length
  • 11 \leq values[i] 104\leq 10^4
  • 11 \leq weights[i] \leq capacity

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy