0/1 Knapsack Problem Using Dynamic Programming - Tutorial & Source Code

01 Knapsack Problem defined and explained. In this tutorial we explain why a greedy rule does not work and present a dynamic programming algorithm that fills out a table. The running time complexity of the dynamic programming algorithm is pseudo-polynomial, not quadratic, even though the table is two dimensional. Understanding the running time complexity gives a sense of why this problem is hard and why it's called "weakly NP-complete".

Source code of minimal implementation in JavaScript:

Source code implementation in Java:

Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

This is a common problem that is given during coding interviews in engineering firms such as Google and Microsoft.

Written and narrated by Andre Violentyev

[burakb]

I am shocked by the contrast between the quality of the video and the number of views and subscribers. I've been watching knapsack problem videos lately because of a homework I had issues with and this video is the only one that makes sense to me.

[pksingh]

This is the best knapsack 0/1 video by far.

[Jerry-ucpn]

Wow, I am astounded at the quality of this video. It explains the concept so clearly and the video editing was great. Thanks a lot. It also helped me for a programming job interview assignment

[ptj]

0:34 interrupted my eternal crankiness.

I hope that you will have the time and motivation to make more of this excellent material.

[kevin_vo]

the clearest explanation on this topic by far! thank you good sir!

[Yaketycast]

I'm so happy I found this channel! Your videos are very well done!

[sodiq_]

Thanks for this. I hope no one broke into your home with this😁

[annakroft]

I watched 5 videos before this and only this one made sense

[JP-icwe]

God bless you zen programmer this information is super useful

[RajanSingh-yqdx]

Just watched the video and subscribed
Keep up the good work sir

[Eggsec]

Thank you for the clear explanation. New subscriber

[pksingh]

Can you please do a video on unbounded knapsack as well? I searched stable sort videos and could not find the unbounded knapsack. Thank you very much for the fantastic video.

[DHRUVNARAYANSINGH]

Great explanation, you just shared jewellery location to thieves 😂😂😂

[Daniel_WR_Hart]

1:02 That's pretty much what I do in Skyrim when looting dungeons with too much stuff

[janezbobic]

Please can you repeat with slow numerical procedure (using numbers please in schedule with Value $100) how to find in previous table with numbers items that we put inside the knapsack to get W and Value 100. I calculated the whole schedule and I have fgot Value $100 using recursive formula. Is the solution item 2 = 4 kg and item 4 is 3 kg or 7 kg from 10 kg? Then I have $ 40 + 60 = $100? Pleae finish your lecture with result. Thanks a lot. JABO