0/1 Knapsack

Try to solve the 0/1 Knapsack problem.

Statement

You are given nn items whose weights and values are known, as well as a knapsack to carry these items. The knapsack cannot carry more than a certain maximum weight, known as its capacity.

You need to maximize the total value of the items in your knapsack, while ensuring that the sum of the weights of the selected items does not exceed the capacity of the knapsack.

If there is no combination of weights whose sum is within the capacity constraint, return 00.

Notes:

  1. An item may not be broken up to fit into the knapsack, i.e., an item either goes into the knapsack in its entirety or not at all.
  2. We may not add an item more than once to the knapsack.

Constraints:

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

Examples

Create a free account to view this lesson.

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