Redirecting to
NADOS


  Prev   Next

0-1 Knapsack Problem







Life is a look a like of pseudo Dynamic Programming

0-1 Knapsack Problem

Welcome back, dear reader. So, how is it going with dynamic programming? Hope you are enjoying these optimization problems that we have been doing till here. Now, here is another interesting and real-life application-based problem. The problem is called 0-1 knapsack problem. Have a look at the diagram given below:

Important Links : Solution Video

img
Problem Discussion :

We are given n items. We are given an array that tells us about the price of those items and we are also given an array that tells us about the weight of those items. This can be visualized as follows:

img

We can visualize this as follows. 2 units weight of the 0th item costs 15 units of money. Similarly, 5 units weight of 1st costs 14 units money and so on. We have a bag and we know the capacity of the bag (we will be given the capacity of the bag). We have to make the price of this bag maximum. For instance, in the above example, we can have only 7 units weight of the items as the capacity of the bag is 7. The maximum price of the bag will be 75. How? Think about this!!!!!! You may refer to the 0-1 KNAPSACK PROBLEM video to understand the problem. Note that it is the 0-1 knapsack problem. Every item can either be selected completely or can be dropped. But we cannot break the item and select it. What do we mean by this? We mean that if we have an item whose price for 2 units weight is 20, then either we can include the complete 2 units weight of the object or we can drop the object (i.e. not select it). But we cannot select 1 or 1.5 units weight of that object. Also, we cannot select a single item multiple times. We can select one item completely and only once.

Method-1: Using recursion and Backtracking
Approach :

A diagram is also shown below to give you a kickstart and help you a little bit in thinking about the recursive approach.

img

This is not the complete Euler tree. It is just a part of it to give you an idea of what we are doing. We either select or reject each element at every level to keep in the bag. For instance, we start with 2-15 means element 0 which has weight 2 and price is 15. If we take it in the bag the capacity of the bag now remains 5 else it remains the same i.e. 7. At the next level if we already took element 0 and we take the next element too, then the capacity becomes 0 and we have to return. So, this is one base case that we can think of. There is another base case. Think of it and write the code yourself!!!


The complete Java code for the 0-1 knapsack problem using backtracking and recursion is given below:

Pseudo Code for Backtracking method
  • Have you thought about the solution to this problem yet? We recommend you to think about this problem once. So, do you know any similar question or similar method by which we can solve this problem? Well, you have solved the problems GET SUBSEQUENCEand PRINT SUBSEQUENCE. This problem can also be solved using the same technique by modifying that method.
  • To give you an idea about that method, what we will do is that we will make a choice at each level of the recursive tree whether an item can be included or not be included taking in mind the capacity of the bag. We will have a lot of base cases reached in our tree. Then we will compare all the base cases and find out the max cost from it. That will be our answer. You may refer to the 0-1 KNAPSACK PROBLEM VIDEO for some hint on the recursion method. You may also refer to the GET SUBSEQUENCE and PRINT SUBSEQUENCE solution videos to understand the procedure of solving such problems.
import java.io.*; import java.util.*; //Backtracking and recursion approach for 0-1 knapsack problem public class Main { static int max(int a,int b) { return (a>b)? a:b; } static int knapSack(int cap, int weight[], int price[], int n) { // Base Case if (n==0 || cap==0) return 0; if (weight[n - 1] > cap) //if weight of nth item is larger than the capacity then do not include it return knapSack(cap,weight,price,n-1); else return max(price[n - 1]+ knapSack(cap - weight[n - 1], weight,price, n-1),knapSack(cap, weight,price,n-1)); } public static void main(String args[]) { Scanner scn=new Scanner(System.in); int n=scn.nextInt(); int [] weight=new int[n]; int [] price=new int[n]; for(int i=0;i< n;i++) { price[i]=scn.nextInt(); } for(int i=0;i< n;i++) { weight[i]=scn.nextInt(); } int cap=scn.nextInt(); int k=knapSack(cap,weight,price,n); System.out.println(k); } }
java; true";

Now let us talk about the dynamic programming approach of the problem.

Analysis
Time Complexity :

The time complexity of this algorithm will be O(2n). Why? Look at the recursion tree and then think about it yourself.

SPACE COMPLEXITY :

The space complexity is O(1) as we have not used any extra space in this approach.

Method-1: Using recursion and Backtracking
Approach :

The analogy to Cricket:

Let's convert this tedious problem into an interesting one for you. Let's convert it into something you can easily think about. Look at the array given above (fig-1). Let us say that there is a team of 5 players (equivalent to the number of items (n)) and let's say that they have 7 balls remaining (analogous to the bag capacity). They have to score maximum runs in those 7 balls (analogous to the maximum cost of the bag of capacity 7). Also, the weight array is analogous to the number of balls a player plays and the price array is analogous to the runs scored by the player in those balls. Have a look at the table given below:

img

Player 0 i.e. the 0th index (in both the price and weight array) can score 15 runs in 2 balls. Player 1 can score 14 runs in 5 balls and so on (Now, don't go into the cricketing logic please! Our bowlers throw a lot of no balls and our batsman can score 15 runs on 1 ball too!!!!). So, did you understand the analogy between cricket and this problem? Why are we doing this? Well, the answer is to simplify the thought process of the solution. We will analyze everything in the form of cricket and because of the analogy, we will be able to solve the knapsack problem as a result. Cool right? Now let's dive into the tabulation method and see how we can solve the problem. You may refer to the solution video to understand the above analogy if you have any doubts regarding it.

Stage 1: Storage and meaning

You are requested to watch the solution video to understand the storage procedure completely in-depth and then move to the further section of the article to study it again quickly.

  • We have made a matrix dp[n+1][c+1] where n is the total number of elements given and c is the capacity of the bag.
  • Let's try to understand first, what is dp[i][j] i.e. any particular element in matrix dp. Look at the image given below:
    • img

The * symbol is kept on an element which shows that if only 3 elements would have been present and the capacity of the bag would have been 5 then at dp[3][5] we would have the maximum cost.

So, dp[i][j] shows the maximum cost if the number of elements are 'i' and if the capacity of the bag is 'j'. This is what each element of this matrix represents.

  • The matrix dp filled completely is shown below:
    img
    Now, let's come back to our cricket analogy and try to understand this in terms of cricket (as well as knapsack simultaneously). The 0th row depicts that there is no player in the team or we can say that there is no element given to us. So, if we are not given any item, how are we supposed to maximize the price of the bag if we don't have anything to keep inside it? So, in this entire row, all the values are zero as there is no element to be kept in the bag and there is no player to make the runs.
  • Similarly, the 0th column depicts that the capacity of the bag is zero or there is no ball left to play in the match. So, in this case, also we can't maximize the cost of the bags or we can say that we can't score any runs. So, this entire column also has all the elements with a value equal to 0.
  • Now, dear reader, we would request you again to watch the solution video ,if you have not watched it as it is difficult to explain each and every entry in the matrix in writing.
  • Now let us try to analyze how we are going to store the numbers in the matrix using loops

Stage 2: Identifying the Direction:

We know that each cell i.e. dp[i][j] shows the maximum cost of the bag when there are 'i' elements in the bag and the capacity of the bag is 'j'. So, the smaller problem is dp[0][0] i.e. we have 0 items and the capacity of the bag is also 0. The larger problem than that is dp[0][1] i.e. the capacity of the bag is 'j'. Even larger problem is dp[1][1], when we have an item to put in the bag and the capacity of the bag is 1. So, the direction of solving will be from dp[0][0] to dp[n][c] i.e. moving row wise in the matrix starting from the first column till the last column.

Stage 3: Traversal in Matrix:

  • The item can be put in the bag only if the capacity of the bag is greater than the weight of the item. Since in our matrix dp, we have started the 'i' and 'j' from 1 but in the actual weights and price array the values start from i=0 and j=0, therefore for accessing an element we will have to subtract 1 i.e. if we want to access weight at position dp[1][1] we will have to write weights[i-1].
  • Since j (the columns), represent the total capacity of the bag at a given time we can put an item only if ( j > weight [ i-1 ])
  • If j is less than weight[i-1] this means that the capacity of the bag is less than the weight of an item. So, we can not put the item in the bag, and in dp[i][j] we will store dp[i-1][j] only i.e. if j> weight[i-1] means that the balls are sufficient for the player so, he can bat otherwise he won't bat and the players before him have batted therefore at dp[i][j] we will store dp[i-1][j].
  • Also if we have kept an item in the bag the capacity of the bag will now reduce. Therefore, the remaining capacity will be j- weight[i-1].
  • Also, when we keep a weight inside the bag then we will check whether we are obtaining the maximum of the bag till now or not. If we are getting the cost higher than it was before including this item, we will update the max cost i.e. dp[i][j] will become dp[i-1][rCap] + price[i-1] where rCap is the remaining capacity of the bag after addition of the item otherwise the max cost will be the same as previous maximum cost i.e. dp[i][j]=dp[i-1][j].
    Note: Dear reader, we request you to analyze this entire story using any method you are comfortable with. If you are comfortable with 0-1 knapsack, analyze everything in terms of it, otherwise, analyze everything in terms of cricket. We also request you to watch the solution video to clear the above concept of traversal in the matrix and write the code.
Pseudo Code for Dynamic Programming Method:
  • Storage and Meaning: Make a dp matrix of size (n+1) x (c+1). Here, each element dp[i][j] stores the max cost of the bag if first 'i' items are present and the current total capacity of the bag is 'j'.
  • Direction of Solving: The direction of solving will be from dp[0][0] to dp[n][c] as the smaller problem is at dp[0][0] as per the meaning assigned to the storage.
  • Traverse and Solve: At every spot, you have to decide whether putting the item in the bag increases the cost oor we shouldn't put it. How will you decide this? Think!!
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] price = new int[n]; String str1 = br.readLine(); for (int i = 0; i < n; i++) { price[i] = Integer.parseInt(str1.split(" ")[i]); } int[] weight = new int[n]; String str2 = br.readLine(); for (int i = 0; i < n; i++) { weight[i] = Integer.parseInt(str2.split(" ")[i]); } int cap = Integer.parseInt(br.readLine()); int[][] dp = new int[n + 1][cap + 1]; for (int i = 1; i < dp.length; i++) { for(int j = 1; j < dp[0].length; j++){ int val = price[i - 1]; int wt = weight[i - 1]; if(j >= wt){ //If the current capacity is greater than the weight of the current item dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - wt] + val); // max cost will be max of cost before putting the item and after putting it } else { dp[i][j] = dp[i - 1][j]; //If current capacity is less than weight do not add item to the bag } } } System.out.println(dp[n][cap]); }}
java; true";
Analysis
Time Complexity :

The time complexity of this method using tabulation in dynamic programming is O(n*c) where n is the number of items given to us and c is the capacity of the bag. This is because we have stored and traversed the values in a 2-D matrix dp which is of the order (n+1)*(c+1). Notice how the time complexity is reduced in comparison with the recursion and backtracking method (which was O(2n)).

SPACE COMPLEXITY :

The space complexity is also O(n*c) as we have created a matrix dp of order (n+1)*(c+1).

So dear reader, we hope that you have understood the method of tabulation for this problem completely. If you have any doubts you may refer to the complete solution video for clearing all your doubts.

Suggestions:

Here are some suggestions from our side that you don't want to miss:

  1. This problem had certain boundaries or limits. We were not able to take half or in general a part of any item and also we were not allowed to take one item twice. What if we do that? We suggest you meditate on this point before moving to the next problem.
  2. We also suggest you revise the TARGET SUM SUBSET and the COIN EXCHANGE PROBLEM after completing this question. This is very essential to understand the point that we have asked you to meditate on and to make your concepts in dynamic programming strong. Till then, Happy Coding!!!
Functions and arrays
Recursion and Backtracking
Dynamic Programming (Tabulation)
Author: Guneet Malhotra
 
Run
Id Name