The 0/1 Knapsack Problem (Demystifying Dynamic Programming)

Try Our Full Platform: https://nas.io/backtobackswe 📹 Intuitive Video Explanations ❓New Unseen Questions 🔎 Get All Solutions I was inspired to do this video after seeing that Tuschar Roy had covered this problem. He did a good job, but I feel it very necessary to stress what is really happening and what each cell REALLY means. Dynamic programming is about subproblems, not remembering patterns to fill cells in with. I watched EVERY ONE of Tuschar Roy's videos and found myself MEMORIZING how to fill out the cells INSTEAD of really knowing what was going on. I hope this video sheds light on what this problem is really trying to express. I talked about the bottom up way to do things. Here is the code for that way of doing it: https://www.sanfoundry.com/java-program-solve-knapsack-problem-using-dp/ You can also do it TOP DOWN with recursion where we investigate all expressions of the subproblems to find the optimal solution. The book Elements of Programming Interviews by Aziz Adnan has a very good version of this. The problem is 17.6 in that book. ++++++++++++++++++++++++++++++++++++++++++++++++++ Question: Write a program for the knapsack problem that selects a subset of items that has maximum value and satisfies the weight constraint. All items have integer weights and values. Return the value of the subset. Can we do it greedily? 0/1 means you cannot split an item. If you could split an item, you could solve this greedily by sorting the item entries by value and then picking from greatest value to least. When you run out of space in your "sack", you'd split the last item and then you would have maximized weight vs value. Brute Force: We could consider all subsets of items in a complete search and take on the cost of exponential time of 2^n (we will explain this in another video). Greedy doesn't work, brute forcing won't make the cut, now what? What can we do now? Dynamic Programming. Notice that we can subproblem this. Dynamic programming is n