Grokking Dynamic Programming Interview/

...

/

Solving the 0/1 Knapsack Problem

Solving the 0/1 Knapsack Problem

Let's solve the 0/1 Knapsack problem using Dynamic Programming.

We'll cover the following...

Statement

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.

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

No.

capacity

weights

Values

n

Maximum Value

1

30

[10, 20, 30]

[22, 33, 44]

3

55

2

5

[1, 2, 3, 5]

[10, 5, 4, 8]

4

15

Try it yourself

Implement your solution in the following playground.

Press + to interact
Java
usercode > Knapsack.java
import java.util.*;
public class Knapsack{
    public static int findKnapsack(int capacity, int[] weights, int[] values, int n){
        // Write your code here
        // your code will replace the placeholder return statement below
        return -1;
    }
}
0/1 Knapsack

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution

We will first explore the naive recursive solution to this ...