20/180: Knapsack Problems Data Structure

Knapsack is one of the important concepts to understand in Dynamic Programming for interview preparation. There are multiple problems available of knapsack variations. Let’s first discuss about the types of knapsack problems

0–1 Knapsack:

In this problem a knapsack is given which has certain limits and we need to choose from the list of items which items should go inside the knapsack so that it can have optimal (min/max/largest etc.) value. The question be like this, an array of items have certain weight will be given and an array of value of those items would be given, and X weight would be given, we have choose those items who can have maximum value and can fit inside the knapsack. In this we have choice weather to pick that item or not depending on its weight and value. Let’s say an items weight is 10 kg and knapsack limit is 9kg, so we cannot take that item and we have to leave it and choose from the other remaining items. And let say there is two items with weight 9kg and one has the value 20 and the other has value 40, in this case we will prefer to put the second item with value 40 as it has maximum value.

For example :

int wt[] = {2, 3, 4, 7, 5}

int val[] = {3, 8, 2, 4, 3}

W = 7.

Here we have weight and value array and knapsack limit is 7. Now we have to choose which items to opt, when you have a choice that means we can use recursion over here. We can either choose the item or not. So first this in recursion is we have to find the minimum value input. in this case it would be n (length of array) = 0 and W = 0,

//because if there are not items in the stack we cannot return //anything and if the limit is 0 in that can we cannot add any //weight inside the knapsack so ultimately resulting in 0.
if (n == 0 || w == 0){ 
    return 0;
}

Now we have the base condition, the next condition we have to check if the weight of the item

if(wt[n-1] <= W){
   //If weight is less or equal we have choice weather to choose the   
   //them item or not. So for that we can find out the max from this
   return max (val[n-1] + knapsack(wt, val, W-wt[n-1], n-1 ), knapsack(wt, val, W, n-1)) ;
}else
   return knapsack(wt, val, W, n-1);

So you our code is finished for the recursive one.

1. Unbounded Knapsack: It is same like 0–1 Knapsack, except that we don’t have limit to choose the item, we can add the same item as many times we want. In 0–1 it was not like that, we have to decide only at the time of choosing the item if we need it or not, if yes then also we will go to the other item to pick, if not then also we will go to the next item to pick. But in unbounded knapsack we can pick the certain item as many time.
2. Fractional Knapsack: Fractional Knapsack is a greedy approach, it doesn’t come in dynamic programming. In this we can divide one item into two depending on the capacity of knapsack. Let’s say Knapsack limit is 9 kg and we have one item of 18kg whose value is 100 and the other item is of 9kg whose value is 40, we can choose the one item with 18kg weight and divide it into have and will add only 9kg in knapsack ultimately having the maximum value i.e. is 50 which is greater than 40.