0/1 Knapsack in 2 Minutes | All you need to know #knapsack #dsa #algorithms #daa #shorts #recap

追加: 2026-05-22

[00:00:00]Hello everyone. Let's just have a quick recap about the 01 knapsack. Say you have a bag which can hold up to some limited capacity and have a lot of items in front of you. Each item having a some weight as well as some profit assigned to it.

[00:00:14]Now, what is your target? Your target is to make sure you'll be picking those items up and be filling your bags in proper way so that your profit is maximized.

[00:00:24]Now, unlike fractional knapsack, in case of 01 knapsack, you cannot pick a item fractionally. You need to either pick it or drop it. That's why it is known as 01 knapsack where zero stands for you're not picking that item and one stands for you're picking that item completely.

[00:00:39]Now, which data structure does the 01 knapsack follows? This particular thing works on the data structure array. That is, there will be a weight array as well as the profit array.

[00:00:48]And which kind of programming paradigm does it follow? This 01 knapsack follows the dynamic programming paradigm.

[00:00:55]Now, if you see how does it work?

[00:00:57]We need to create our DP table, that is dynamic programming table.

[00:01:02]Where the column will be the maximum capacity of the bag, the rows will be each and every item, and each of the cell will be indicating the highest profit at that certain point.

[00:01:14]Now, what are the things you need to do here? If you really look into it, whenever you see item, you have two options in your hand. You're either picking it or you're dropping it.

[00:01:24]So, you need to fill that DP table accordingly.

[00:01:27]If you're taking it, if you're picking it, in that case, you need to subtract the weight of that item from the remaining capacity of your bag. And for that, the profit will be added up. And if you're not taking it, if you see that that that particular element, if you pick it, it is not getting you more profit, then you simply ignore it. Then you simply copy the value from the previous cell or from the left hand side cell. So, you have two options, you need to pick the maximum [laughter] out of it. So, this is the formula for this one.

[00:01:55]Now, if you want to see what is the time complexity of this one, you need to create a DP table and there what is the number of how many number of column and how many number of rows will be there, that is dependent upon the maximum capacity as well as the number of elements. So, the time complexity becomes order of n into w, where n is the number of elements and w is the highest capacity.

[00:02:18]So, that is all about say that 0/1 knapsack and we have also discussed how it is different from the fractional knapsack.

[00:02:24]Now, a dedicated complete video about this topic is already available in my top playlist. I am putting it up in the pinned comment. You can check it out.

[00:02:33]Thank you for watching and stay tuned for the next videos.