You clearly explained what is the purpose of "w-wi" in B[i-1, w-wi]. It comes at 4:40. I have spent so much time reading PDF after a PDFs, including the one shown in this video. I think Profesorrs at university should "come out their box" and take a fresh look at their PDF.
This was the EXACT content I was looking for. This video helped me understand this concept and pass my semester too. Btw I saw this nearly 3 years ago and came back to say "Thanks".
you should work on your explaining skills because you tend to stammer a lot but other than that, i think this is the best video on knapsack i've found so far so thanks! :)
i started watching after reviewing all negative comments....after urs i started to watch and thankyou for your honest comments.it helped me to understand
If this were an unbounded knapsack problem, would row 1, column 4 have a value of 6? Because the weight of the first item is only 2 kg and in the 4th column, our knapsack has a capacity of 4 meaning 2 kg is still left. Therefore another copy of the first item can fit? Obviously, more changes would occur throughout the table but I am just giving one example. I am just trying to understand this for my own sake.
Nice explanation, but could you/somebody interpret the final result? Im wondering how we can judge about the optimal choice based on the last cell in the table?
I still have a doubt..can u please help? While doing the calculation for 2nd item.. on the 4kg why did you subtracted 3 from 4 and got the weight 1Kg left..!! I mean our max weight is 5kg..so if we want to check how much more weight we can take we should do 5-3=2Kgs instead of 4-3=1kg ..Right?? Plz help!
1 question..when we are taking weight 4kg with 2 items, its ok that we took benefit of 7 for 3 kg but for remaining 1kg why are looking for its benefit in previous row , previous row was for 0 items,isn't it??
Very nice explanation. I appreciate your efforts ! Can you give the link to the material/slides you are referring in the video? It will be of great help !
Hello apu, at 10:14 you said as its 4th kg you are taking the item containing 4kg and wrote benefit 5. However, I can take the item of weight 2kg which has the benefit of 3 and go back to the cell 2 and add the benefit. 2kg(3)+ Benefit of Cell(2) [For 4th kg] 3+3=6 So, shouldn't I take 6 instead of taking 5? Can you please give the feedback as soon as possible, I have CSE221(Algorithm) exam tomorrow. Thank you! :)
Thanks :). How do i backtrack and find out what items you need to pick to get the max weight? This algorithm gives us the max weight he can carry; But what items should he select to get that weight which was obtained ?
how can i can i solve this problem if M=165. n=6, (p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,73). solve knapsack problem using dynamic programing.
For anyone who didn't understand by watching the video, try making a table yourself. This helped me to figure it out (with the help of the video, of course.) Basically, the way it works is that the previous row is the optimal solution for every weight limit, assuming that only the items of that row and up are available. So the 0 row, all the answers are zero because there are zero items available to take. The 1 row is the maximum value for every weight limit from 0 to 5 when only item 1 is available. The 2 row is the maximum value for every weight limit from 0 to 5 if only items 1 and 2 are available. And so on. So for any given cell in the table, to find what the value should be, you compare the values if you don't take the current row's item (which will be equal to the cell above it) compared to the value if you do take the current row's item (which will be the sum of the value of the current item plus the cell from the above row at the weight limit which is equal to the remaining amount of weight that you can carry after taking the current item.) And trying to work out the problem by hand helped me to understand why this is reasonable.
At 6:33. you considered weight 4 - 3 = 1kg, for 3kg weight benefit is 7 and for 1kg benefit is 0. so 7+0 =7, benefit for 4kg. Why didn't u considered 3+1=4kg, for 3kg weight benefit is 7 and for 1 its 0, 7+0 = 7??
Idk where this particular problem comes from but it makes things more tricky than they need to be. Why in heaven would a bag of 4kg of gold have a lower benefit then a bag of 2kg?
Wow, i got it right away. I am asking myself is it real algorithms or ???? cos i have seen other video which i don't understand. U are my hero. THanks a lot!!! how about if the question is minimum weight?
Maybe u should give pseudocode for i: = 0 to M do cost[i]: = 0; for j: = 1 to N do /* each of item type */ begin for i:= 1 to M do /* i means capacity */ if i - size[j] > = 0 then if cost[i] < (cost[i - size[j]] + val[j]) then begin cost[i]: = cost[i - size[j]] + val[j]; best[i]: = j end; end;
I am so glad someone finally explained how the table worked! I've staring at them so long confused as to what was going on. Thank you so much!
No one was able to make me understand this knapsack but u did it very well mam...thankful to u...lv u tc.. ☺
Thank you, it will surely help for tomorrow's exam.
You clearly explained what is the purpose of "w-wi" in B[i-1, w-wi]. It comes at 4:40. I have spent so much time reading PDF after a PDFs, including the one shown in this video. I think Profesorrs at university should "come out their box" and take a fresh look at their PDF.
This was the EXACT content I was looking for.
This video helped me understand this concept and pass my semester too.
Btw I saw this nearly 3 years ago and came back to say "Thanks".
Worth adding for completion that if weight < 0 in the table the value is minus infinity. So that when w-w_j < 0 the value is not taken.
you should work on your explaining skills because you tend to stammer a lot but other than that, i think this is the best video on knapsack i've found so far so thanks! :)
Francesca Popescu no. balbalbalbal
Eduard Stanciu boss asta chiar explica bine :))
i started watching after reviewing all negative comments....after urs i started to watch and thankyou for your honest comments.it helped me to understand
this video saved me in the last moment from my exams...Thanks
The video is so good.I understood the topic very well. The approach is exemplary
Best explanation of 0-1 Knapsack so far... Thank You.. :)
that's seriously great tutorial with proper explanation of examples...without a bit of confusion..thanks :)
Well, that helped. Term Final is near and that was a savior. Thank you!
Thankyou so much for your help :) Awesome tutorials :D Please keep uploading more. LOVE THEM!!
thank you so much for uploading this video. you have no idea how much it's helped me!!!
very nice explanation much better and shorter than other videos can be used in exam as time is less there
I understand this algorithm because of you , thank you.
Thank you so much for your video that helps me unwind this twisted Knapsack problem!
thank you, The better explanation than i have ever seen
Good job mam! but i have a question tell me the pros and cons of knapsack, coin changing, cutting rod problem.
thanks a lot ...
its gonna work in my semester exams .great job
for weight =4 max item =2 he can also take 2 weight+2weight = 6 benefit instead of (3+1) wight = 4
+keshav aske Har item ki quantity one hai, bruv.
for item 2 weight is 3kg so subtracting 4-3kg= 1kg which eventually gives 0 and 0(1kg)+4(3kg)=4
Knapsack problem is no more problem for me ..
thaks for this upload
If this were an unbounded knapsack problem, would row 1, column 4 have a value of 6? Because the weight of the first item is only 2 kg and in the 4th column, our knapsack has a capacity of 4 meaning 2 kg is still left. Therefore another copy of the first item can fit? Obviously, more changes would occur throughout the table but I am just giving one example. I am just trying to understand this for my own sake.
I have a stupid question. (Well ,it probably is....) Are you supposed to sort the items by weight before using the algorithm to create the matrix?
You saved me from my exam.
Thanks.. A short and sweet description. :)
you are too fast.. but this helped me understand this problem way better than any other lessons.. thank you so much
Very nice explanation........tommorow is my exam....
Hi can I know which software you used for recording the screen and also the software that you drew the problem on. Just for my course project. Thanks.
I've been looking for it. thanks heaps
This explanation was so clean
Why is it 4-2 here?
9:47 I mean like, why did we take 4-2 =2. And then get 3 from row 2 and add that to 4 to get 7, here?
Why is it not 1kg remaining?
Nice explanation, but could you/somebody interpret the final result? Im wondering how we can judge about the optimal choice based on the last cell in the table?
what if there is another constraint such as cost?
I have a doubt, how to solve it if the knapsack capacity is a fractional value eg. 5.5 kg ?
I still have a doubt..can u please help? While doing the calculation for 2nd item.. on the 4kg why did you subtracted 3 from 4 and got the weight 1Kg left..!! I mean our max weight is 5kg..so if we want to check how much more weight we can take we should do 5-3=2Kgs instead of 4-3=1kg ..Right?? Plz help!
for the "column 4 kg". u can take total 4 kg highest. that's why it's 4-1. If we did it for "column 5 kg", it would be 5-3.
Thanks a lot Madam. Excellent Explanation.
1 question..when we are taking weight 4kg with 2 items, its ok that we took benefit of 7 for 3 kg but for remaining 1kg why are looking for its benefit in previous row , previous row was for 0 items,isn't it??
I loved this video , great work
Very nice explanation. I appreciate your efforts ! Can you give the link to the material/slides you are referring in the video? It will be of great help !
2017 ..still best vid on knapsack
Hello apu, at 10:14 you said as its 4th kg you are taking the item containing 4kg and wrote benefit 5. However, I can take the item of weight 2kg which has the benefit of 3 and go back to the cell 2 and add the benefit.
2kg(3)+ Benefit of Cell(2) [For 4th kg]
3+3=6
So, shouldn't I take 6 instead of taking 5?
Can you please give the feedback as soon as possible, I have CSE221(Algorithm) exam tomorrow.
Thank you! :)
Thank you ! You are my life savor
THIS WAS VERY HELPFUL.
Thanks :). How do i backtrack and find out what items you need to pick to get the max weight? This algorithm gives us the max weight he can carry; But what items should he select to get that weight which was obtained ?
Why does the beneffit of 5 change from 9 to 6? shouldnt it be (5,9) ??
Thanks alot dear...I'm grateful for your help. :)
So, should the items be sorted by weight?
tnx....Dat helpd for my tomm's Exam.....Tnx Alot,,,
If you were on item 2, why were you looking at item 3?
I think You should first explain the recursive relation before applying it to fill the table.
what if the total weights and items are given as 100 50 20 10 7 3.??? can u gimme the solution?? how do I compute it in table??
how can i can i solve this problem if
M=165. n=6,
(p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,73).
solve knapsack problem using dynamic programing.
VERY WELL EXPLAIN.....THANK YOU SO MUCH...
Thank you very much :D
keep it up!
For anyone who didn't understand by watching the video, try making a table yourself. This helped me to figure it out (with the help of the video, of course.)
Basically, the way it works is that the previous row is the optimal solution for every weight limit, assuming that only the items of that row and up are available. So the 0 row, all the answers are zero because there are zero items available to take. The 1 row is the maximum value for every weight limit from 0 to 5 when only item 1 is available. The 2 row is the maximum value for every weight limit from 0 to 5 if only items 1 and 2 are available. And so on.
So for any given cell in the table, to find what the value should be, you compare the values if you don't take the current row's item (which will be equal to the cell above it) compared to the value if you do take the current row's item (which will be the sum of the value of the current item plus the cell from the above row at the weight limit which is equal to the remaining amount of weight that you can carry after taking the current item.)
And trying to work out the problem by hand helped me to understand why this is reasonable.
Thank you!
At 6:33. you considered weight 4 - 3 = 1kg, for 3kg weight benefit is 7 and for 1kg benefit is 0. so 7+0 =7, benefit for 4kg. Why didn't u considered 3+1=4kg, for 3kg weight benefit is 7 and for 1 its 0, 7+0 = 7??
thank you so much. It helped a lot
Great video, helped a lot ^^!
I love you. Thank you so much!
Awsome explanation .... :)
Thanks for sharing! :D
Thank You.. but I hope it could have been explained in much more fun fashioned way!!
U EXPLAINED WELL.... THANX
nice explanation, and i love ur voice
Love you !! tut is awesome ..
That really helped! Thank you!
well explained... thanks a lot..
very good explanation
apu is it a top down approach or a bottom up ??
Its tabulation or bottom-up approach....:)
Thank you ma'am... understood :-)
Idk where this particular problem comes from but it makes things more tricky than they need to be. Why in heaven would a bag of 4kg of gold have a lower benefit then a bag of 2kg?
Wow, i got it right away. I am asking myself is it real algorithms or ???? cos i have seen other video which i don't understand. U are my hero. THanks a lot!!! how about if the question is minimum weight?
I would guess the minimum weight is always zero...
Thank u for such a nice tutorial...
please share your blog link..
thanks.. needed it :)
dear mifta you are ausam
Thank you
You're Welcome!
Thank you so much :)
Very Helpful. :-)
good explanation.......!!!thank U....
I have absolutely no idea what any of that meant. Sounded good though lol
Maybe u should give pseudocode
for i: = 0 to M do cost[i]: = 0;
for j: = 1 to N do /* each of item type */
begin
for i:= 1 to M do /* i means capacity */
if i - size[j] > = 0 then
if cost[i] < (cost[i - size[j]] + val[j]) then
begin
cost[i]: = cost[i - size[j]] + val[j]; best[i]: = j
end;
end;
+Thanh Nguyen I agree.
really i enjoyed it :)
Thank you!
very helpful :)
No traceback?
Superb.... helpfull
good one ...keep it up
plz can u give me its complete algorithm....!!!
so they that we can relate each steps will solving rhe example..
u have done a great jpb..!!!thank you
"column 5 kg + column row - 6 kg + 1 = 10 kg so we keep 10 kg because 5-2 = 3!"
Fuck
Thanks a ton.
Exzamp i meant 1000 khey gee
hmm I never used this in class Thanks
Tysm!! it was good ...
ThanQ....
so fast come on girl,slow down,keep calm and tech calm :)
perfext
nice job
thanks :)
2nd diagram no way as clear as the first. Other than that good stuff
waita basa, thank you
Mifta Apu ROCKZZZZZZZZZZ