Knapsack problem

#1

I am not able to find the recurrence relation

#2

Hi @sahazeer123 , this is a very classic dp problem that one should know , for this problem you need to have a proper understanding of 0-1 knapsack problem . So, lets begin() with the solution

what we have to do is fill m stones ,out of n stones , of different colors with least space left in the knapsack , we are given the knapsack capacity, the weight and color of each n stones

Now we have two approaches

  1. consider each n stones one by one and insert it into our knapsack and check each time if the color of the stone is present in the knapsack or not and weight does’nt exceed our knapsack
    so the states are ,
    i) index of the stone [0-(n-1)]
    ii) current weight of knapsack [0 - X]
    iii) set containing the colors present in the knapsack [2^m]

    So, even after using dp we will get exponential time complexity

    So what should we do ?? let’s look at second approach

  2. we will do reverse mapping of colors and index of stone
    i.e for each color we will store the stone index with that color this can be easily done using 2D vector
    So, what we can do is for every color i we will loop through the stones having color ci and insert it into our knapsack and call for color i+1 and return the min space left
    States are :-
    i) the index of color (1-m)
    ii) the current wt of knapsack (1-X)

so the complexity after using dp will be O(m*X) which is just what we wanted

here’s the code
here colorMat is the mapping of color to stones
colorMat[i] is the vector containing the stones with color i
ksWeigh is the current weight of knapsack

int colorfulKnapsack(vector<vector<int> >&colorMat,int i,int m,vector<int>&wt,int ksWeight,int X){
    if(i==m){
        return X-ksWeight;
    }
    int ans=INT_MAX;
    for(int j=0;j<colorMat[i].size();j++){
        int clrWt=wt[colorMat[i][j]];
        if((ksWeight+clrWt)<=X){
            ans=min(ans,colorfulKnapsack(colorMat,i+1,m,wt,ksWeight+clrWt,X));
        }
    }
    return ans;
}

Here’s the full code :

In case of any doubt feel free to ask :slight_smile:
If you got the answer mark your doubt as resolved
if you liked the answer then hit a like :+1:

1 Like
#3

Can you please share any variation of knapsack problem ?

#4


this blog has some good variations
you can also try google kick start 3rd problem

1 Like
#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

1 Like