The 0/1 Knapsack Problem (Demystifying Dynamic Programming)

👉 NEW VIDEO & CODE: https://backtobackswe.com/platform/co... (free)


Free 5-Day Mini-Course: https://backtobackswe.com
Try Our Full Platform: https://backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓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-progr...

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 not about stupid magic tables that you see people fill out, it is not about guessing. DP is about remembering the solutions to subproblems so that we can find the globally optimal solution. We just subproblemed this recursively.

This is where the table comes from. Each cell MEANS SOMETHING.

IT IS THE ANSWER TO THE QUESTION.

If we solve all the subproblems and remember all answers then we will find the globally optimal answer.

The subproblems are represented by what is called a recurrence equation.


Complexities

n = total items
m = max weight (max weight constraint)

Time: O(nm) (we will be solving this many subproblems)
Space: O(nm) (we will store the results of n*m subproblems)


++++++++++++++++++++++++++++++++++++++++++++++++++

HackerRank:    / @hackerrankofficial  

Tuschar Roy:    / tusharroy2525  

GeeksForGeeks:    / @geeksforgeeksvideos  

Jarvis Johnson:    / vsympathyv  

Success In Tech:    / @successintech  

++++++++++++++++++++++++++++++++++++++++++++

The 0/1 Knapsack problem is question 17.6 in the fantastic book Elements of Programming Interviews.