Please check out this code

#1

https://ide.codingblocks.com/s/263586.What’s the problem with this code

#2

Okay the way you are proceeding with the question is incorrect , knapsack is 2-D dp , and not 1-D dp.
So you will have to drop your approach even if you correct the segmentation fault.
Please see this code https://ide.codingblocks.com/s/263703

The code explanation
dp[index][rem] contains the max value you can obtain if you are allowed weight equal to rem, and are considering elements from index to last element.
so your answer is stored in dp[0][W]

if (item[index][0] <= rem) dp[index][rem] = item[index][1] + calc(index + 1, rem - item[index][0], n, item);

This line states that if the current weight of the item at that index is less than rem and we can pick it up,
we pick it up and move forward to index + 1 and reducing rem.

dp[index][rem] = max(dp[index][rem], calc(index + 1, rem, n, item));

This line is for the state when you don’t pick up the current item and move to next item.

Please dry run the code, this is how we are supposed to write knapsack.

#3

Thnx Devwrat for the help…Yeah I got it completely wrong but I got it now…

#4

https://ide.codingblocks.com/s/263586.This is bottom up approach of the same problem.What’s the problem in this code

#5

@aryan hey let me check your code.

#6

@aryan hey there is problem in your logic of filling array ,dont take max in last just fill dp in that way by taking max in each term while filling and just return dp[n][w].Check this code for more understanding:
int knapSack( int W, int wt[], int val[], int n)

{

int i, w;

int K[n + 1][W + 1];

// Build table K[][] in bottom up manner

for (i = 0; i <= n; i++) {

for (w = 0; w <= W; w++) {

if (i == 0 || w == 0)

K[i][w] = 0;

else if (wt[i - 1] <= w)

K[i][w] = max(

val[i - 1] + K[i - 1][w - wt[i - 1]],

K[i - 1][w]);

else

K[i][w] = K[i - 1][w];

}

}

return K[n][W];

}

#7

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.

#8

And 1 more doubt -----> 2-D matrix ko main function define + input leke

#9

int maxCost( yaha kyaa aayega , int n)

#10

@aryan hey yha pr func(int a[][size],int n) size woh jo tumne niche main me define kia hai max limit ka lena acc to constraints.