Recursive approach

#1

i haven’t used dp as of now in this code but by using recursive approach it’s giving segmentation error.

#2

Hey @akshatkaush, the problem with the code is the recursive calls are not correct, for every item there’ll be two recursive calls

  • Taking that element, adding its value in answer and reducing the weight of the particular item from the cap, value[n-1] + cal(cap-wt[n-1],wt,value,n-1)

  • Not taking the current item into consideration, 0+cal(cap,wt,value,n-1)
    The answer will be the maximum of the above two cases.
    Hope this helps.

#3

this is with the 0-1 knapsack problem not with 0-n knapsack

1 Like
#4

the approach should be,
dp[i] = max(dp[i], dp[i-wt[j]] + val[j]), 0<=j<=n-1 and wt[j] <= i.
for reference you can check out the code. This is the bottom up way of solving the same, but still the you can check the relation between the problem and it’s smaller subproblem.