0-1 Knapsack Problem

0-1 knapsack problem

We have already discussed the Fractional Knapsack Problem in the previous post of the Greedy Algorithm tutorial. In this post, we will discuss another famous problem 0-1 Knapsack Problem.

0-1 Knapsack problem is similar to Fractional Knapsack Problem, the problem statement says that we are basically given a set of items whose weights and values are given. We are also given a knapsack which has some capacity, the knapsack can’t store capacity beyond it.

Our aim is to collect maximum values in the knapsack.

NOTE here we cannot collect items partially. we only have two options, whether to pick the item completely or leave the item. This is why this problem is called the 0-1 Knapsack Problem, either you pick the item or don’t pick it.

Consider an example of a knapsack containing coins, we cannot break or divide a coin partially, either we have to take the coin or leave it.

I hope
the Problem Statement is clear to you.

Analysis of the Problem Statement

Let us understand the problem statement more clearly by taking an example.

0-1 knapsack problem
0-1 knapsack problem

In this above example, the optimum solution would be by taking item 2 and item 4, the output will be 90.

NOTE that here we have only two choices, either to pick the item or leave the item.

Naive Solution of 0-1 Knapsack problem

As we know that we have only two choices, and we have to collect maximum possible values in the knapsack within the knapsack capacity, we will use recursion to solve this problem. We will run recursion from backward.

This problem is similar to the problem of finding all possible subsequences of a string.

Let’s see the recursive code for 0-1 knapsack problem,

int knapsack(int weight[], int value[], int capacity, int n)
{
        if(n == 0 || capacity == 0) return 0;

        if(weight[n-1] > capacity) {
              return knapsack(weight, value, capacity, n-1);
        }

       else {
             int case1 = knapsack(weight, value, capacity, n-1);
             int case2 = value[n-1] + knapsack(weight , value, capacity - weight[n-1], n-1);

             return max(case1, case2);
       }
}

Let us understand the code clearly, initially we have weight[ ], value[ ], capacity, and n (number of items).

It’s clear that if (weight of the item > capacity), we will not consider that item as it violates our capacity limit.

Now, we already know that there are only two cases possible, so we will consider both cases –

(i) In the first case, we will not consider the nth item, so we will simply call recursion to the remaining (n-1) items.

(ii) In the second case, we will consider the nth item. So after consideration, capacity will reduce to (capacity – the weight of that item) and we will also add up its value to the result.

We will again call recursion to the remaining (n-1) items by updating other parameters.

Time Complexity of Recursive Solution : O(2^n)

Let us understand this recursion by considering the above example,

0-1 knapsack problem
0-1 knapsack problem

Now let run the recursion for the above example,

I hope it’s clear how Recursion is taking place.

We can observe that there is an overlapping subproblem in the above recursion and we will use Dynamic Programming to overcome it.

Dynamic Programming Solution of 0-1 knapsack problem

As recursion proceeds, we observe that there are overlapping subproblems present and it is no point to solve the same subproblems again and again.

Let us now see the DP code,

int dp[n+1][capacity+1] = {-1,-1,.., -1};

int knapsack(int weight[], int value[], int capacity, int n)
{
        if(n == 0 || capacity == 0) return 0;
        if(dp[n][capacity] != -1) return dp[n][capacity];

         if(weight[n-1] > capacity) {
                 dp[n][capacity] =  knapsack(weight, value, capacity, n-1);
         }

         else {
                int case1 = knapsack(weight, value, capacity, n-1);
                int case2 = value[n-1] + knapsack(weight , value, capacity - weight[n-1], n-1);

                dp[n][capacity] = max(case1 + case2);
         }
         return dp[n][capacity];
}


This is a Memoization based Solution (Top Down). It is similar to the recursive solution only difference is that we are storing the solution of subproblems into some array or hash map so that whenever we need the solution of that subproblem again, we can use this data instead of calculating it again.

Time Complexity of Top-Down Solution: O(n.capacity)

Bottom-up (Tabulation) based Solution

This Solution is similar to top-down solution, the only difference is that we fill an array in a bottom-up approach, which means we first fill the array considering that there is only one item available to us, then we fill the array considering that there are only two items available to us and this way we fill the entire 2-D array.

Let’s us see the code,

int knapsack(int weight[], int value[], int capacity, int n)
{
	int dp[n+1][capacity+1];
	memset(dp, 0, sizeof(dp));

	for(int i = 1; i <= n; i++)
	{
		for(j = 1; j <= capacity; j++)
		{
			if(weight[i-1] > j) dp[i][j] = dp[i-1][j];
			else {
				dp[i][j] = max(value[i-1] + dp[i-1][j-weight[i-1], dp[i-1][j]);
                             }
                }
        }
        return dp[n][capacity];  
}

Let us understand the code more clearly, we have created a dp[][] 2D array of size [n+1][capacity+1], one extra space for storing base condition and after that, we have followed the same steps that we have followed in memoized based approach.

Let us understand it by an example,

0-1 knapsack problem
0-1 knapsack problem

We will make a table for this above example,

0-1 knapsack problem
0-1 knapsack problem

Here row denotes the item and column denotes the capacity.

Let us understand the table more clearly,
dp[1][5] denotes that by considering the first item, maximum how much value we can earn by a knapsack of capacity 5.
dp[3][7] denotes that by considering the first 3 items, maximum how much value we can earn by a knapsack of capacity 7.

We will get the answers to the above Question by following the bottom-up Dynamic Programming Algorithm.

Time Complexity : O(n.capacity)

I hope this problem statement(0-1 knapsack problem) and its DP solution is clear to you all.
That’s all Folks..!!!

Try some sliding window technique problem here

Tagged : /

Leave a Reply

Your email address will not be published. Required fields are marked *