Doubt in answer part

#1

did ot unerstand the logic behind max(include exclude )
can you please explain

#2

Here in 0-1 Knapsack problem ,for each item you have a value and weight associated with it. For a knapsack of a given capacity you have to fill items in it in order to maximize the total value.
So, first thinking recursively in a Top Down manner, you have 2 options at any point-

  1. Either pick up that item only if its weight< capacity of Knapsack
  2. Do not pick up that item
    So you can make recursive call for both the queries and find the maximum among both the queries.In each call modify the left over capacity of the knapsack if you have picked up that item.
    The recursive function would look something like this-
int knapsack(int * weight, int * value,int i,int n,int capacity)
{
if i==n or capacity==0 //Base Case
return 0;
int q1=0;int q2=0;
if(weight[i]<=capacity) //Means you can pick up the current item at position i
q1= weight[i]+ knapsack(weight,value,i+1,n,capacity-weight[i]);
q2=knapsack(weight,value,i+1,n,capacity); //Not picking up that item
int ans=max(q1,q2);
return ans;
}

You can memoize this using 2D array where i and capacity would be the parameters.

#3

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.