The Knapsack Problem

The Knapsack Problem is a classic problem in computer science - You have a knapsack and several items to pack into it. Each item has a weight and a value, and you can only carry up to a maximum weight. Find a combination of items to pack, such that you remain under the weight limit, but you maximize the value of the items selected. ERRATA NOTICE: Please check the pinned comment for errors and corrections in this video. While seemingly straightforward, this problem requires a surprising amount of thought to solve! In this video, we look at the naive recursive solution first, before moving on to a far more efficient dynamic programming solution! = Timestamps = 00:00 Introduction 00:47 Contents Page 01:33 Definition of the Knapsack Problem 02:16 Why a greedy solution wouldn't work 03:34 Introduction to recursive solution 04:17 Visual explanation of recursive solution 10:47 Final recursive trace (if you want to skip the explanation and want to just see it happen) 12:33 Python code for recursive solution 20:22 Complete Code 21:27 Discussing other variants (eg. Multiple selection variant) 22:45 Discussion of Time Complexity / Efficiency 23:56 Dynamic Programming Solution - Description of Memo Table 26:00 Dynamic Programming Solution - Decision making process 28:52 Dynamic Programming Solution - Full Trace 34:32 Dynamic Programming Solution - Conclusion & Time Complexity 35:38 Conclusion = CODE DOWNLOAD = To view and download the code written in this video, check out the following Bitbucket repository: https://bitbucket.org/nerdfirst/knapsack-problem To download, first click on "Downloads" in the left sidebar. Then, in the subsequent page, click "Download Repository". = 0612 TV = 0612 TV, a sub-project of NERDfirst.net, is an educational YouTube channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more! Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe! Like what you see? Buy me a coffee → http://www.nerdfirst.net/donate/ 0612 TV Official Writeup: http://nerdfirst.net/0612tv More about me: http://about.me/lcc0612 Official Twitter: http://twitter.com/0612tv = NERDfirst = NERDfirst is a project allowing me to go above and beyond YouTube videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources. Watch this space, and keep your eyes peeled on this channel for more updates! http://nerdfirst.net/ ----- Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.