The 0/1 Knapsack Problem (Demystifying Dynamic Programming)

📹 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.

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)

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

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

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

[BackToBackSWE]

Table of Contents: (my bad if I'm loud, this video is old and the YouTube algo keeps feeding it)

Problem Introduction 0:00 - 2:38
Walkthrough One Subproblem 2:38 - 4:38
The DP Table Introduction 4:38 - 6:12
The Recurrence Relation 6:12 - 8:30
What Each Cell Really Means 8:30 - 9:08
Solving The Dynamic Programming Table 9:08 - 16:46
Finding The Items That We Chose 16:46 - 18:32
Gearing Your Mind For Other DP Problems 18:32 - 19:07
Time & Space Complexities 19:07 - 19:45
Wrap Up 19:45 - 20:10

This is the 0/1 Knapsack Problem. The key is to see the subproblems. DP is just something that takes seeing a lot of problems to get a solid grasp of. I still do not have a full grasp of the subject myself.

[amitpurohit]

I have seen very few people with this level of passion for teaching....Thank you sir for teaching so passionately!!!

[siddharthkhandelwal]

Every other YouTuber: "In this DP problem, just do this math, and the problem is solved."
Back to Back SWE: Explains why we do every step.

I've watched a lot of dynamic programming (DP) videos, but only your videos have given me a clear understanding of each step. Using the thought process from your videos, I have been able to successfully solve all DP problems with complete intuition.

[architjindal]

I think the best channel related to coding. He explains everything in a really good way.
Thanks a lot Benyam Ephrem.

[internetmaster]

I just came across your channel and I would like to show my appreciation for what you do. Your energy and enthusiasm when explaining these problems is contagious! Super helpful for someone who is learning programming from scratch. Thank you for your hard work!

[philipfemo]

I have never been this stressed watching a programming problem explained lmao

[daisyallday]

Wow you're so brilliant. Thank you for slowing down this problem for me. I was so confused in class 😂

[ak-hjxw]

im glad I've found your channel, this problem was giving me a HEADACHE yesterday, and you're the only one who explained it in such a brilliant way so far!!! i hope I also understand the asymptotic notations from you, they've given me a heart ache for the ENTIRE semester ughhh!!

[dannythi]

I love the way you teach. You break down the problem and at each point repeat what is happening so it stays in your head. Keep doing what you do.

[choibreandan]

your explanations are much better than others teaching dp on youtube, not going to name names (I'm sure you know) and you deserve a medal

[lavenderrose]

*It will take a month to grasp this problem*
Me: *Watching it one night before my exam*

Though, I got the idea man! Thank you :)

[tuandino]

Im telling you im scrolling through these knapsack videos on youtube, and yours by far are the easiest to understand. I wont need to scroll anymore

[punitpawar]

Hello there, On LeetCode there is a question - Target Sum -Find out how many ways to assign symbols ( - + ) to make sum of integers equal to target S. Can this be solved with the same approach as explained in this video ? Will you be able to share your thoughts or put a video for this ? Here is the problem are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

[BharCode]

I think, to approach this problem from DP table perspective is a little difficult intuitively.
My approach is, just recursively solving sub problems like Climbing stairs or Egg Dropping.

First define *base cases*
*Case1* : if the weight capacity is 0, then we can’t choose any item. Hence the optimum value is 0;
*Case2* : if the number of items is 0, then we can’t choose any item. Hence the optimum value is 0;

*Other cases*
*Case3* : if the weight of the Nth Item is greater than the max weight capacity, then, we have only one option, i.e. NOT choose that item, but to choose from remaining(N-1) items for the same weight capacity.

*Case4* : if the weight of Nth item is equal to or lesser than max weight, then we have the 2 options.
Either to choose the item or Not to choose.
But the decision to be made is depending on whether we get max value by choosing Nth Item or not choosing the item but choosing from the remaining (N-1) items.
i.e
If we choose Nth item, then value1 = (value Of Nth Item) + (optimum Value from remaining N-1 items for the remaining weight).
If we don’t choose Nth item, then value2 = (optimum Value from remaining N-1 items for the max weight)
Now our optimum value is max(value1, value2);

private static int optimumValueRecursively(int n, int maxWeight ){
//Base cases 1 and 2
if(maxWeight==0 || i==0){
return 0;
}

//case 3
if(weights[n]>maxWeight){
return optimumValueRecursively2(n-1, maxWeight);
}
//case 4
int optimumValue =
Math.max((values[n]+optimumValueRecursively(n-1, maxWeight-weights[n])),
optimumValueRecursively(n-1, maxWeight));

return optimumValue;

}

There is no DP table involved in the above solution, DP table is useful when we consider memoization.

[estebanlopez]

I love your passion, man. Not only great teaching, it's also fun to watch you!

[IanHuang-chcn]

This is the best DP problem explanation video I've ever watched! I can say 90% of instructors in the universities couldn't do better than you bro. Salute! Hope you can continue to make awesome videos!

[nabihs]

Not having the items in order by weight is a great touch 👌
Thanks for doing that. Intuitively, people would assume they have to which really doesn't change the result.

[brandonbarrett]

This is the probably the 4th or 5th explanation of the knapsack problem that I've watched in the past few days. THIS is one where I had the moment of epiphany where I said "OH... I get it." Thank you.

[uddipta_g]

After multiple videos and almost giving up on it since a year, I finally understood 0/1 Knapsack.

[ikhitishpanigrahi]

I just wanted to make a point clear that here it is a bounded knapsack...so we cannot use the weights in the same row again and again along the row for different weights of the bag..that the reason we go 1 row up when we go "w" weight back in a row...pls correct me if I am wrong..