0/1 Knapsack Problem Top Down Dynamic Programming

Solving 0/1 Knapsack problem using top down dynamic programming with memoization

[tonyjiang]

Thanks a lot Tushar Roy, this really helps, at first I feel like you are repeating the same ideas many times which wastes time. But later I found this is the right way to deepen my understanding of a problem. Patience is needed in solving the problem, once you understand the process. Next time it will be very easy for you. Thanks a lot Tushar!

[ivsaimanoj]

very clear explanation and good quality code that we are not finding elsewhere.. thanks Tushar!

[PrakashKumar-ofzs]

As I think, we should consider Index class having
1. remaining weight
2. Set of remaining items

reason behind it is --- we may end up with same number of remaining items, but different set of items. As each items holds different weight and value, so it should not be correct to consider different sets as same based on size of set.

It is really impressive to see the structure of map here.

Please correct my understanding if I am going wrong. Thanks for your time and efforts.

[MohammadMahadiHassain]

ঠুসার ভাই, আপনার ঠিউটোরিয়াল অনেক ভাল,

Nice Explanation, Thumbs Up From Bangladesh

[TheTutorialspoint]

tushar your explanation is owsome and far better than any most of the college make more vids if possible make codechef longchallenge vids also

[AromonChannel]

You sir, just got a new subscriber! Grear job! You are very good at explaining things

[Neithan]

Tushar! Thank you so much for your videos. I believe I'll be here for a long time. Do you take requests?? :) I am really looking forward to if you will be able to do a tutorial on the Bellman-Ford algorithm. Please continue what you do. Thank you again! :)

[alizaman]

Thanks Tushar for explaining it so well.

[YanuarTriAdityaNugraha]

Nice intro to the DP algo design. Maybe you could add a pop-up text at the beginning to say that those value numbers were actually the weight, and vice versa :)

[venkateshwarancholan]

Worst-case Time complexity: O(n*n)
Worst-case Space complexity: O(n*n)
explanation: there are 3 cases
w<n: for w< n, w is the bottleneck so, time and space becomes O(w*n)
w==n: O(w*n) = O(n*n) obvious
w>n time complexity becomes O(n*n) as n*number of possible subtractions(which is also bottlenecked by n)

to understand better think of w>>n like w = this wouldn't affect the problem's run time complexity and space complexity(for hashmaps)
Iterative bottom up is always O(w*n) but not top-down which at worst case in O(n*n)

if we are using 2d array for space in top-down, space complexity becomes O(w*n) and out of which only n*n values are filled.

[iamdipankarj]

It seems that top down method is easier than bottom up approach.

[giantstride]

How can we modify the knapsack solution to take care of the problem if the total weight or knapsack capacity is large but the total sum of values of weights is less

[ratebsairawan]

many thanks, i`ll probably watch all your videos .Very helpful !!

[MrDivad]

How can we show that this algorithm has a running time of O(weight + numItems)?

[NNareshKumar]

Hi,

Can you explain a problem where you need to optimize cost C wrt two weights w1 & w2?

[caitancorreia]

Can you please do a video on 4 vertices network using backtracking please...cant seem to find it anywhere

[wwwwwww]

Here we have checked for a and b but what about other two c, d, I mean that when a is not included and b is not included when bag can hold weight of 8 and 2 items c, d are untouched. Why that is not shown in state space tree?

[patelprincy]

Tushar Roy plzz post the video on knapsack problem using backtracking.

[drama.sreerama]

why dont we take c or d as the first objects and check those possibilities

[dheerajsaini]

U explained it very clear. The thing i want to know why you say if we pick weight 8 and 2 items the best we can get 9. It should be wrong because we can get 13 from it. Please clear it. I know u meant to if we pick c and d with weight 8 the max we can get is 9 but i want to cross check it. Am i r8 ?