0/1 Knapsack : A Dynamic Programming Story

Mrityunjay Vashisth
Oct 4, 2019 · 5 min read

If you are here, you are also haunted by the fact that why is 0/1 Knapsack a dynamic programming problem. Answer you get when you ask why it is a dynamic programming problem includes;

  • It has overlapping subproblem.
  • It has optimal substructure.

Okay, so if a problem has overlapping subproblems, can it be a dynamic programming problem ?. Yes. It is a case of divide and conquer algorithm where the subproblem repeats itself and storing the result of a subproblem is a good idea. Overlapping subproblem check.

We can use greedy approach to solve a problem that exhibits optimal substructure if we can prove that every step in the our greedy algorithm is optimal. Then when does a problem becomes a dynamic programming problem ?. Let us try to solve 0/1 Knapsack greedily.

Greedy Approach to 0/1 Knapsack

Consider the following problem

The Knapsack capacity is 15 and we have three objects that we can choose from. We compute the profit to weight ratio for each object to make our greedy choice.

Going with greedy, we first select B2 since it has highest profit/weight ratio.

  B1 B2 B3    
( 0, 1, 0 )
Remaining Knapsack = (15 - 7) = 8
Current Profit = 35

Now we have a Knapsack capacity of 8 and two objects that we can choose from. B3 has next highest profit to weight ratio, so we will try to take object B3 into our knapsack.

  B1 B2 B3
( 0, 1, 1)
Remaining Knapsack = (8 - 8) = 0
Current Profit = 35 + 40 = 75

We get a max profit of 75 with the greedy approach. With brute force we can check that the maximum profit that we could have is 75.

Greedy works !!!!

Or does it.

Let us take a slight variation of the above problem.

The Knapsack capacity is 15 and we still have three objects to choose from. What’s changes is the profit associated with object B1. It has changed from 40 to 60.

Going with greedy, we first select B1 since it has highest profit/weight ratio.

  B1 B2 B3    
( 1, 0, 0 )
Remaining Knapsack = (15 - 10) = 5
Current Profit = 60

Now we have a Knapsack capacity of 5 and two objects that we can choose from. Upon inspection, we can see that we cannot put any of the remaining objects into our Knapsack since the Knapsack capacity (5) < weight of any of the remaining object. So we get a maximum profit of 60.

Is it optimal. Is this the maximum profit that we can have. Let do a brute force on the above problem.

If we take object B2 and B3,
Weight of B2 + B3 = 15 == Knapsack Capacity.
Profit Gained = 35 + 40 = 75

Wait a minute, did my greed stoped me from getting maximum profit. Maximum possible profit is 75, but our greedy approach is giving us 60. Seems like greedy approach might not give optimal results.

Greedy approach does not work with 0/1 knapsack always. We might end up in local optima.

Divide & Conquer to 0/1 Knapsack

We know dynamic programming is a case of divide and conquer with overlapping subproblem. Let us see how is 0/1 Knapsack have overlapping subproblem. There can be only two possible case when we want to divide the problem of 0/1 Knapsack.

  • The object is put inside the Knapsack
  • The object is not put inside the Knapsack

Let us consider another example to understand overlapping subproblem

We have five objects. Let us divide the problem to see if it have overlapping subproblem.

Knapsack 01KS(m, n)
Parameters:

m = capacity of Knapsack
n = No. of objects
Wn = Weight of nth object
Left Subtree:
01KS((m - Wn), (n - 1))
Right Subtree:
01KS(m, (n - 1)

Using above constraints, we build a recursive tree in a bottom up fashion.

  • Non overlapping node are represented by green node.
  • Overlapping node are represented by blue node, with red node being repeated.

In the above recursive tree, function calls in red are repeating the blue nodes. Divide and conquer with overlapping subproblem, Dynamic programming is that you !!!!.

Divide and conquer with overlapping subproblem is a candidate for Dynamic programming.

Brute Force Divide & Conquer with Memorization : Dynamic Programming Approach to 0/1 Knapsack

At this point we have a clear idea of why and how 0/1 Knapsack is a Dynamic programming problem. Let us dig deeper to do some analysis on our problem.

The recurrence relation for 01 Knapsack will be;

For n objects      :      n + 1 level complete binary tree.
n + 1 level : 2^(n+1) - 1 number of nodes.
2^(n+1) - 1 nodes : 2^n function calls.
Time Complexity : O(2^n)
Space Complexity : O(n)

How many distinct function call are there in 0/1 Knapsack.

01KS (m, n) = (m + 1) * (n + 1)
= O(mn)
where m is capacity of Knapsack and n is number of objects.

If we run different inputs for 01 Knapsack problem, we will notice that there is very less repetition. Because of this reason, memorization does not help much in bringing down the time complexity.

01 Knapsack is one of the NP-Complete problem.

Bubble in a Nibble

All things life