Part 53 - Knapsack Problem by Branch & Bound Technique

Added: 2026-05-20

[00:00:00][music] Everyone in this video I'm going to explain about NAPSA problem by applying branch andbound technique. It is another algorithm design technique. Already in my previous video I already explained what do you mean by napsack problem and how this knapsack problem can be solved by applying brute force technique and how the same knapsack problem can be applied by applying dynamic programming technique. See this dynamic knapsack is also called as 01 knapsack that also we discussed. Okay. And the same napsac problem how to solve by uploading greedy technique that is also called as greedy napsac or fractional napsac both are same greedy or fractional napsack. So we already solve this problem by three methods one is brute force another is dynamic programming and is greedy technique. So now same problem we are going to solve now by applying one more technique called branch andbound technique. Okay. So the difference between dynamic knapsack and as well as fractional knapsack is only in fractional knapsack it is allowed to take some part of the item some part of the item. Okay. But in dynamic and as well as in this branch and bound technique either we need to select the complete item or we should not select that means we cannot take some part or some fractional part of the item we cannot take. That's for the branch and bone and as well there's a similarities between branch and bone as well as uh dynamic napsack. Now let us suppose for [laughter] the beginners those who don't know what do you mean by napsack problem napsack means a carryback that's it okay in general English meaning napsack means carry back so we have one carry bag we have one carryback of some capacity maximum capacity M that means this max this napsack can have some capacity say for 10 kg or 20 kg that's what the maximum napsack capacity M and we have any number of items We have n number of items or you can say n number of objects or elements you can call whatever we have n number of objects. Now each object is having some weight. So okay suppose now I'm taking this marker this is one object or this is one item this is having some weight and if you take this board this is one item and this is having some weight like that if you take any object every object is having some weight and as well as every item is having some price some value that means the price of this uh what marker is say 20 rupees price of this board is say for example 800 rupees like that each And every item is having some price. That's all for the items. So we have given n number of items where each item is having its own weight and each item is having its own price and given napsack of capacity m. This is the problem statement. What is the constraint? Now what we need to do out of this n item we need to select few items in such a way that we should get the maximum profit. We should get what?

[00:03:14]Maximum profit and whatever the items we selected that weight total weight of the selected item should be less than or equal to the maximum napsack capacity that mean that should be fit within the napsack we should not overflow okay overflow so that's what the problem statement so objective of the problem is maximum profit so here again see whatever the problem we are solving by applying branch and down technique We are constructing one state space tree.

[00:03:46]In that state space tree for each and every node we need to calculate one bound value. For this example bound value will be the upper bound because we need maximum. In the previous video we discussed about the traveling salesperson problem. There we need to find out the shortest distance. There the boundary is lower bound but here the boundary is upper bound. So we need to calc up calculate the upper bound for each and every node. Formula used is upper bound UB is equal to total profit obtained plus total weight of the napsa capacity that's what the M what we are carrying that is a total capacity you're calling W you can call M also not a problem m or W whatever total napsa capacity minus total weight of the selected objects into value of the next item vi + one divided by weight of the next item. This is the formula what we are using in order to calculate the upper one. Okay.

[00:04:55]Now very simple see now here V indicates what? Capital V indicates the total profit or the final profit. Okay. Now capital M indicates a maximum knapsack capacity.

[00:05:15]So small W indicates weight of the selected items.

[00:05:22]Weight of selected items.

[00:05:26]Okay. Then VI + 1 indicates value of next item. That means I + 1 item means next item.

[00:05:38]Similarly, W I + 1 means weight of next item.

[00:05:46]Weight of next item. These are the terminologies. If you remember this formula is enough. So you should know all these things. Now I will take one example and for that example I will show you how to calculate the upper bound as well as how to write the state space tree. Assume this is the given problem.

[00:06:04]Okay. Given number of items is what?

[00:06:06]Four. That means one first item, second item, third item, fourth item. And given weight of each item, weight of the first item is 4 kg. Weight of the second item is 7 kg. Weight of the third item is 5 kg. Weight of the fourth item is 3 kg.

[00:06:21]So this is in terms of kgs. Okay. And say price is rupees. That means price of first item is 40 means 40 rupees for 4 kg. 42 rupees for item 2 which is 7 kg, 25 rupees for 5 kg item 3, 12 rupees for item four that is 3 kg. Now for this given problem what is the first step is you calculate price per unit weight price per unit weight you calculated that means given the prices for this many cases now you calculate what is the price for 11 1 kg items. Okay. So this is 4 kg 48. So 4 40 by 4 4 how much? So this is four that is 10 that is 10 rupees per 1 kg. So for 4 kg 40 rupees.

[00:07:09]Similarly 42 by 7 that is 6 that means it is 6 rupees per kg. This is 5 25 by 5 it is 5 rupees per kg. 12x3 4 rupees per kg. Now you calculate what is the price per unit weight that is for one kg how much you calculate and after calculating you need to sort these elements in the decreasing order because decreasing order means first item will be the maximum that will the first item but luckily for this problem it is in the decreasing order only this column this column decreasing order suppose for any other problem you won't get this is in a decreasing order accordingly You sort it in decreasing order. But for this problem, no need. If it is already sorted in a decreasing order, no need.

[00:07:57]Problem is solved. Otherwise, you need to sort this item according to the decreasing order according to the price per unit rate. Okay. Now assume given maximum capacity of the nutsack is say 10 kg. This is the given problem. Now I need I will write the what state space tree. Okay. For the state space tree I will write. Now initially I not started.

[00:08:19]Now I need to start start I need to so now what is the upper bound for the beginning that I need to find out okay upper bound to calculate now what is the formula of upper bound this is the upper bound okay initially see I I'm not s anything that means see my napsack is what empty my napsack is empty this is my m is equal to 10 kg profit price is equal to zero total weight of the seed because I' not selected anything weight is zero. Now my I value is zero because I have not selected any of the item I value is zero. Now I apply this formula upper bound for this one. Okay. Now here I will write for this upper bound upper bound U is equal to what is the profit I get since I noted any item I is equal to Z. I is item in question? I is 0. This is zero plus okay 0 plus now maximum capacity is what? M 10 kg 10 minus weight of the selected items. How many items I selected? Nothing I selected. So zero okay into V value of I + 1. I value is what? Zero. I right now I not selected any items. Z + 1 V value of 1.

[00:09:33]That means value of 1 is what? 40 divided by weight of I + 1. I is 0. I + 1 is what? 0 + 1 W1. So v_sub_1id by w1 this was v1 by w1 40 by 4 4 by 4 this is nothing but 10 10 into 10 100 100 + 0 100 so this is your 100 now my upper bound value is 100 initially I have not seed anything this is the first step now this is the first node root node of the state space tree now what I will do now I will decide now the item in question is what I is equal to 1 that means now I'm checking this item I is equal to 1.

[00:10:12]I is equal to 1. That means whether can I take this first item or not. So I have to decide if I include this first item into my napsack I will get maximum profit or if I leave this first item I get the maximum profit. Okay, that I need to check. So what I will do? I will take two things. One is with item one.

[00:10:36]With item number one because I equal to one without item number one with item one without item one. Now what is the lower bound that I need to calculate now?

[00:10:52]Now now suppose if I take this item with item one with item one. If I include item one nack is empty. No, item one I included. Assume I included item one.

[00:11:04]Assume I included item one. If I include item one. If I include item one, what is the weight of item one? 4 kg. Remaining capacity is now only 6 kg. Remaining capacity 6 kg. Now total weight is four and profit if I inate first first item if I include I'll get price of 40. So I'll get price is 40. I will get okay 40 profit. So I'll update. Now I'll calculate the formula here. Okay, I'll calcate formula here. Now upper bound for here upper bound is equal to value what 40 plus 10us if I include this this item is having how much item is 4 kg. So 4 kg 10 - 4 10 - 4 into I equal to right now what I is equal to right now 1. I is equal to right now 1. I is equal to 1. V of I + 1 means 42. I 1 1 + 1 2 V2 value of 2 is 42 divide by weight of second 42 by 7. So 42 by 7 is 6 6 this is 10 - 4 6 42 by 7 6 into 6 36 36 + 40 76 this is my upper bound. This is when this is when you take the first item with item one. That means when you got the profit is what value what we get for 40 I will get weight of certain item is what 4 kg this is the node one next now without item one without item one means I'm not taking any item if I'm not taking any item means no profit again value is zero I got profit I zero I got since I'm not selected item selected item weight is zero can upper bound okay upper bound for this Upper bound for this one is again value 0 10 - 0 because 10 is a maximum my maximum capacity W is selected weight because I not selected anything so 0 into next item I = 1 I = 1 1 + 1 2 okay so W value 2 by this one so 42 by 7 is 6 so 10 into 6 so is upper boundary 60 now now among these two nodes which is the maximum node so that means which node is on the maximum value 76 so I am not expanding this one I'm expanding this one so I decided that I'm including item one so if I include item one item one I included if item one is included this is the case that mean remaining capacity is 6 kg my total selected weight is 4 kg profit 40. So that means I item one is in selected. Now next is now I value becomes what? Two. Now I value becomes two. Next item. This is done. Now I have to check second item. So now I have to decide whether I need to go for with item one or without item one. So I will check it out. This is with item two. This is without item two. Without item two.

[00:14:25]Okay.

[00:14:27]Now I need to calculate this values.

[00:14:33]Okay. Now what is the total weight of the selected items? See I'm coming from this with item one. With item one weight of the set is four. Now if I include item two, item two weight is about seven. 7 + 4 already is 11 which is greater than the maximum capacity. So it is not feasible solution. So I'm not calculating anything because here no way I'm not calculating already. This is with item one. Wait with item one already is four with item two. Next if I said item two item two is 7 4 + 7 11. So if I include item two it is overflow.

[00:15:12]Maximum UPS is 10 kg but it become 11 kg. So it is not feasible I cannot select. So I decided with item without item without item two means with item means maximum profit I write as of now 40 only weight is equal to four only.

[00:15:28]Now I have to calculate the lower upper bound. So now again upper bound here is equal to upper bound is equal to now profit is what we place 40 plus 10 minus weight W is 4 into I value right now 2 I + 1 means 3 W V3 by W3 means 25 by 5 25 by 5 this is 5 5 into 6 30 + 40 is 70 so upper bound is 70 okay now this is to 17 this is only one option now I will decided not to go with item two without item two so that means item two I'm not selecting so next the item in question is what item three now I is = 3 now I is equal to three now now when I is equal to three now I have to decide now again two options are there for me one is what with item three with item three.

[00:16:35]Another one is without item three.

[00:16:43]Now again I need to calculate the low upper bound for these two nodes.

[00:16:48]Now with item three means already weight is how much? Four. with item three means item three value weight is five. 3 + 5 8 3 + 5 8.

[00:17:02]So then value is what? Its value is 25.

[00:17:06]25 already got 40. So it should be 65.

[00:17:09]It should be 65. So now for calculate the upper bound for this one. Now upper bound for this one is value 65 plus now 10 - 8 10 - 8 means 2 into value of next item that is I + 1 I equ= to 3 V4 by W4 that is 12x 3 12x3 is also 4 so 4 so 4 2's are 8 8 + 7 6 it is what 73 it should be 6 4 2 8 Oh yeah 65% 73 so upper bound is 73 now I calculate without item three without item three that means already you return the same thing value 40 weight is equal to four now it's upper bound it's upper bound is equal to 40 + 10 - 4 6 into next item 12x3 4 this is 4 24 + 6 240 this is 64 okay now out of this which is maximum this is maximum so I decided not to expand this I'm expanding this one so this I included item three item three so now if I included item three here item three item three already included item one this is the status now item three value weight is five okay now it is totally 5 + 4 9 kg 9 kg. Okay. 5 + 4 is 9.

[00:18:47]9 kg. So this profit is 25. So it is 65.

[00:18:52]So now remaining 6 - 5 1 kg is remaining. 1 kg is remaining. So now you calculate for the again two options.

[00:19:00]Okay. Two more things are there. Now this is with item four without item four. Okay. Now if already weight is 9. Now if you include item four, item four is 3 kg. 3 3 + 9 12 kg so this is greater than 10 maximum maxa capacity so it is violating the rules problem constraint so I'm not doing this one so now I have to go for without item three so here it value is already I'm retaining this only weight is equal to 9 value is equal to 65 now calculate the upper bound now the final upper bound is equal to value is 65 + 10 - 1 10 maximum nity capacity minus W is 9 into next item or E is equal to 4 next item nothing is there so zero this is nothing but 65 so now maximum profit is 65 that means 65 is the maximum profit for that I include only item one and item three I included these two items are included but I have not included what item number two and four so this is how to calculate Okay. So again I'm telling suppose in the exam you got a problem in which it is not sorted you have to sort it. Okay. So this is what the branch and you try with other examples. If you have any questions please write it in the comments. Thank you. Thanks.