0-1 Knapsack Problem - Dynamic Programming

Discussion of the 0-1 (Integer) Knapsack, a known NPC problem. Through use of dynamic programming we are able to calculate an optimal solution in pseudo-polynomial time.

[@christopherschoeder6781]

for future videos, I would recommend having a "draw screen" or having a cursor to show which value you're showing. Otherwise rambling off numbers for someone who's trying to understand both the concept and what the publisher is saying can be difficult to interpret

[@MsClrs]

The best video for the knapsack problem. Great work!

[@yasmeennaseer]

Truly understood dynamic programming for knapsack for the first time in my life!!

[@blindprogrammer]

thanks, every good video! if possible, can you please tell me which software did you use to build this video?

[@christiansakai]

So you guys are students who teach! amazing!! very very good videos!

[@heisenburger311]

Watching it double times makes me understand much more.

[@SKPSonaipatty]

good work, thanks a lot.

[@pauliewalnuts6734]

great video thanks champ :)

[@ianbolfa]

Thanks a lot!!!

[@debarkasengupta5351]

The optimal substructure description part is unclear.

[@huxi8070]

Hi, I have problems to understand which values do you take into account when calculating the Cell [2,6]. Could you please explain? I think I dont understand the variables. If "v" is the value, what is "c"? Is "M" the Max value? Is wi the column index? Thanks

[@megmeyers3432]

Zuzana Dee I agree. This is unclear.

[@shawnscientifica6689]

Meg Meyers So what's going on here is you make a matrix. The rows are the item number. You start with 0 (no item at all) and go up to how many items you have. In this case we have 4 items so we go from 0-4. Ok. Now we need columbs.The columbs are starting from a smaller weight and going up to our Max weight. Why? Well, if we pick (imagine you need to steal jewels from a tomb but can only carry so much weight) if we pickup all the most valuable jewels and don't go over for the smaller weight then we can make a mental note of this for when we get stronger and can pick up more jewels. At that point you can remember that back when you weren't so strong you could get $X of valuables. With that information you can decide if it makes sense to put down an item and pick up a heavier item (where you'll get more money) or not even bother (all the other stuff is too heavy and replacing one of the jewels you had before makes you leave with less $$$) so basically you're using it as a stepping stone. Ok, now you go up in the columbs up to the real maximum weight you can carry, now you will be able to make the best decision based on all those past mental notes of less weight problems. The answer is the one in the last row and column. Hope this helps.

[@sanjaykg10]

can u please tell me how to solve 0/1 Knapsack Problem using merge and purge method

[@dmitriimarkov7067]

Would be better if you had more animations. For example, when you say about particular cell in the table, color it so it can be distinctive from other cells.

[@sid9860]

where is fractional knapsack problem video :( ???

[@x87-64]

Just greedily take the ones which have largest value/weight ratio.

[@Mike-ci5io]

- The max=13 in the beginning should be described as the max weight the bag can handle not "value" - Doesn't the greedy approach pick items 4 and 2 (has the next big ratio) instead of 4 and 1. w4 + w2 < 13?

[@jack_galt]

+Intelli Vester 2's ratio is 4/6 = 2/3, as opposed to 1's ratio of 5/5 = 1, so 1 is taken.

[@flyingSapo]

Why is it "pseudo-polynomial time"? That was never explained...

[@CSBreakdown]

+yoDood Hi! Thanks for watching our video. We have a separate video dedicated to the explanation of Polynomial time algorithms vs. Pseudo-Polynomial algorithms. You can check it out here: kzbin.info/www/bejne/p3fIc3eeYriil6M

[@flyingSapo]

Thanks for the response! Keep up the great work! Your videos really helped me understand better.

[@MsClrs]

I have a question, position (2,4 ) should be 4. Right?

[@shawnscientifica6689]

MsClrs Well let's see. So we are looking at item #2 which is a Gem that weighs 6lbs and is worth $4. Since the columns are the weight (we start from smaller weights and make note of the maximum $$$ we can get at that weight for deciding when we can carry more stuff) We realize at row 2 (looking at items 1-2) and column 4 (when we can only carry 4 lbs) we see we can't take item #2 since it's 6lbs. So we look at item #1 which is 5lbs. So we are too weak to carry anything so we leave the mystical tomb with nothing but a story (0$)

[@MsClrs]

Shawn Scientifica super!! Thanks a ton 😊

[@jiap2uw]

Is c[i][M] = c[i-1][M] if wi < M instead of wi > M ???????????????

[@shabyparveen1649]

3rd will be applied.

[@emirbalic8800]

very good. clear and confident. thanks

[@saffaura]

I had headphones in... And the volume turned up... And my ears are bleeding after that intro. Major yikes.

[@anuraggupta8197]

Dued, our intro suck. My ears are bleeding