0-1 Knapsack problem - Inside code

NB: This video is ad-free, you can choose to support Inside code by purchasing one of the courses above or dropping a super thanks!
NB2: Discounts of courses above are permanent

[sproga_]

It was interesting to see an actual mathematical solution to this. I've been solving stuff like this w/ Excel's Solver for years

[anishlushte]

Need correction in code to check if weight is becoming negative before adding.
let values= [ 60, 100, 120 ];
let weights = [ 10, 20, 30 ];
K = 50
code will return 280 instead of 220.

Fix: if (weights[i] > k) return knapsack(values, weights, k, i+1)

[ibrahimshehuibrahim]

Hello everyone this is the correct solution
def knapsack(values, weights, k, i=0):
if i == len(values):
return 0
elif k < 0:
return float("-inf")
elif weights[i] > k:
return knapsack(values, weights, k, i + 1, )
else:
return max(values[i]+knapsack(values, weights, k-weights[i], i+1), knapsack(values, weights, k, i+1))

[coding]

There is a small mistake:
`if(k<0) return INT_MIN; `
must above
`if(i == size) return 0;`

Because when we at the last item, sometimes we must not pick that item due to the smaller capacity of the bag. Thus `max(pick, nonpick)` must equal to 0. If you put ``if(i == size) return 0;` at the top, `max(...)` will always equal to values[i].

[abdulrehmanamer]

Bro you really made my day..
I was stuck on it since the day
Alhamdulillah!

[lordsixth]

Cant thank you more just wanted this problem to understand dp . Lot of love to you

[leenavig]

very brilliantly explained. Lot of hard work to put this video together. Thank you for your effort!

[Have_a_moment]

doubt:
how do i known which elements i have selected when i found max total value.

[jimbobago]

FYI: dollar signs are written *before* the number - $20, not 20$.