0-1 Knapsack


Problem Statement :

There are N items, numbered 1,2,…,N. For each i (1≤i≤N), Item i has a weight of Wi and a value of Vi.

We have to choose some items among them so that total weight of the taken items in knapsack should not exceed W.

N and W will be given to us.

Find the maximum possible sum of values of items without violating the conditions mentioned above.


Naive Approach :

· We can take each subset and then we can check whether the given conditions satisfy or not.

· If a subset satisfies the given conditions, then we may update the maximum value, depending upon the total value of the items included.


Time Complexity :

· In each step, we have 2 options either to take the item or not.

  • There are N items.
  • So, a total of 2N possible subsets are possible.
  • Hence, the time complexity is O(2N) which is exponential.

· We can do better than that using the same approach. Let’s see how!!


Optimisation :

· We just have to store the previously calculated values so that we need not to calculate the same values again and again.

· Suppose I am starting from index 0 and as mentioned in the problem I can take atmost W weight.

· Now I am at index 0 and I have two options : either to take the item or not. If take the item then I can take atmost W-w[0] in the knapsack.

· If I don’t take the item, then I can still take atmost W weight in the knapsack.

DP State : dp[x][y] where, x refers to the starting x items considered till now and y refers to the maximum weight capacity that knapsack can still have after considering first x items.

Recursive Condition : The maximum value that can be obtained from ‘n’ items is the max of the following two values :

1. Maximum value obtained by n-1 items and weight W (excluding nth item).

2. Value of nth item plus maximum value obtained by n-1 items and W minus the weight of the nth item (including nth element).

Base Case : When number of items included is 0 then the value should be 0 or when the weight remaining is zero then also value should be 0.

Edge Test Case : When weight of nth item is more than ‘W’ then we cannot include it in our knapsack and hence we are left with only Case 1 ,i.e, to exclude the nth item .


Time Complexity :

  • Maximum value of x possible is N.
  • Maximum value of y possible is W.
  • So, the time complexity is O(N*W).

Code :

Input format :

N W

W1 V1

W2 V2

…….

Wn Vn

Code:


Happy Coding 😊

By Programmers Army

Contributed by Shubham Kumar