About the logic 2 of knapsack prblm

#1

I didn’t understand the 2 nd logic of this qstn

#2

Hey @Senjuti256

image
image1614×1022 317 KB

Here We are defining dp in other way

  1. defines dp[i][w] as the maximum value we can get with some subset of first i items and weight exactly w
  2. This states the reccurenece relation
    So two choices we pick the ith item
    then vi + dp[i-1][w-wi]
    or we don’t choose it
    then dp[i-1][w]
    so dp[i][w] will be max of both the cases
  3. tells what the answer will be since we can choose with at most weight W
    hence we can iterate on all dp[N][x] where x belongs to 0 to W and maximum among them will be our answer
  4. tells the base case when only 1 item then dp[1][w1]=v1 and dp[1][x]=0 for x!=w1
#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.