0/1 knapsack problem-Dynamic Programming | Data structures and algorithms

hi guys today's topic is knapsack problem so in this problem what is there you are given some items with their weights and profits okay some items will be you will be given with their weights and profits and one container you are you are given or you can say one knapsack say simply knapsack is what it's like a bag that you carry on your back or you can say shoulders okay so suppose one container or one bag is given whose weight is also given or you can say the size of this is also given some kgs this w will decide the maximum size to store these items okay now what is this problem basically you have to select some items from the given items and you will put those items into this bag or you can say container okay and you have to select these items such that you will get the maximum profit let us suppose you have chosen some items from this and you have you have put these items into new into your bank and suppose you are going to sell these items then I put a say item select Carney hey when you will sell these items then you will get the maximum profit okay this is the knapsack problem suppose where it is given what 20 kg so you can select any number of items but the total number of weight of the selected items would be less than or equal to 20 because octopus egg bag had this map you can carry only 20 kg weights okay so up with nahi items up to choose cursor thousand car total number of weights of those item would be 20 kg taco se select carnea so that the make the profit would be maximum so two types of knapsack problem are there one is 0 and knapsack problem and second one is fractional knapsack problem okay so today we'll discuss what zero-one knapsack problem what is there in this problem either you can pick the item completely or you will not pick the item means either 0 or 1 0 means appaluse item copic nahi kiya 1 means you how picked that I you can say the complete item suppose one item is having great 2kg okay one is having made three kg so you can pick this item so you have to pick that item completely means you have to pick 2 kg of this item you cannot pick that you you cannot pick 1 kg of this item okay 1 kg omnipeek earlier 1 kg Jordy I know know the items would not be divisible you will have to pick that item completely ok let us suppose some individual things like laptop a complete laptop HEPA karna padega you cannot pick the screen up nificantly bucket scotch or dia or you can say mixer EPCOT will be a complete pick an operator something like that ok so that is 0 1 knapsack problem either you will pick that item completely or you will not pick that item ok that is 0 & 1 EPSA perhaps our problem fractional make out that you can divide that item suppose one item is of 3 kg you can pick only 2 kg of this item and you can left 1 kg okay it's not compulsory that you have to pick 3 kg of this item this is the fractional knapsack problem and this is solved with what greedy method and zero-one knapsack problem and will be sold with dynamic programming method okay so we'll take one example and we'll discuss the zero-one knapsack problem so let us take an example here weights are given 3 4 6 & 5 profits are also given 2 3 1 4 okay and the W is given what 8 suppose we are taking 8 kg weight is given 3 kg 4 kg 6 kg and 5 kg and the weight is w is what 8 kg or you can say that bag in which you'll store you will pick the item and you will keep that items okay that bag is having capacity 8 kg okay and here we have number of items what for number of items we have fine now one method is what you can write in it you can say X I suppose X is any item we will write what like this 1 0 0 1 it means the happy one height means we have selected in the first item we haven't selected second item we haven't selected the third item we have selected what fourth item having read five something like this will write the answer in this form one and zero phone okay now if you have total number of items for then how many combinations would be possible suppose one combination is zero zero zero one another one is zero one zero one something like this we have four items now having weighed three four six and five so total number of combination would be 2 raised to power 4 that is 16 ether you can make the 16 combinations and you can check which combination you will select so that you will get the maximum profit okay our second approach is what will solve this method using what dynamic programming approach now what is dynamic programming approach I have told you many times that in dynamic programming the complicated problem will be divided into sub problems and ultimately when you solve the subproblems then you will use the solution of the subproblems and ultimately you will get the result of or you can say the solution of the complicated that final problem okay you will not solve the complete problem at once we divide that problem into sequence of steps fine now how this problem would be solved using dynamic programming approach now the very first thing is you are supposed to draw a matrix okay now this is the matrix you have drawn say this side we have taken what from 0 to 8 because total weight is given is what 8 your backup capacity wait total maximum capacity is what and then you'll write from 0 to 8 okay now this side we have taken what waits and profits and the one variable that is I I would be from 0 to 4 first we'll write go to 0 then we have 1 2 3 4 4 items then in 0 to 4 that total would be 5 total number of items plus 1 here we have written what weight of each item and here we have written what profit of each item and see these weights should be written according to their or you can say and in ascending order weight is three four six and five but I have written here what three four five six five six they should be in increasing order or you can say the ascending order okay now according to that you will write the profit two three four and then one now you will fill this table well you are not taking the complete weight at a time see we have divided this problem into the sequence of steps eight sub steps first we'll take the weight total weight suppose we have zero then we'll increase the weight one by one and these are the sub problems this answer of sub problems would be you know written in the these columns or cells and finally here in the final cell you will get the answer okay because finally weight is what it now let us start how you will fill this table first row and first column would be what column would be able to zero because weight is what zero you are taking a bag having there to 0 then obviously well no we cannot select any item okay and first row also would be what first draw make it happen a pass we have we have in if we don't have any item because here what we have 0 we don't have any items so we don't know right what 0 this is what for 0 and is 0 first one first column now you have to fill these got these cells have you will fill this one find out here what we have weight is what I weight of item is what three now we have only one item of in a well of available set we have got one item having weight three we don't have these items okay these below items we have only one item because I value is what now one this is I value 0 1 2 3 4 and this is the value of this W 0 to 8 now if you have one item having 8 3 okay and the weight of the bag is what the capacity is what one can you fill a bag having capacity 1 kg with a item having weighed three kg no we cannot fill so we will write here what 0 now here what we have a bag of capacity to we cannot put this item having weight three see because it's zero and knapsack problem up core Jelena here to complete three easy appropriate aapke and Kaka okay up iske you're either you will pick that item completely or don't pick that item okay our simple trick is if weight is three then up to zero to two you will write what the above values to copy the value of above cell 0 0 into 0 now at 3 now you have a bag of capacity 3 and weight of that item is also 3 you can pick this item obviously we can keep this item here if you will pick that the site and then profit would be what - then here you will write what - okay now in this case we have a bag of capacity for obviously we can put we have only one item having date trees and we can put this one then profit would be would be what - so here also - here - here - and here also will have two because we have only one item that is having bid three so grab three may poop curse at the auto four five six seven eight maybe I was kaput curseth you next is what I value is increased and I value is now what - okay now we have two items we have one is item having made three one is having I have eight four now you have to fill this one total weight is what we have one bag having size what 1 kg can we put this one this item having bit 4 kg no we cannot put this item here okay so what you will do here is you will write what the value of the above cell that is 0 okay now weight is what only two can you put this item no we cannot select because weight of this item is for that is greater than 2 can you select this item no we cannot select this one because through is also greater than 2 so will write here what 0 our simple step is what if this weight is 4 then from 0 to 3 0 1 2 3 less than this for you will copy the all values from the above cell that is from 0 1 2 3 here what you will write we will copy the value from the about cell okay now for the same we have two items now one is having made three one is having wait for and the total weight is what for now we have two choices either he will select this one or you will not select this one if you will select this one here then the profit would be what three okay and three plus what you have to do is you have to find out maximum three plus you will go one step up and what you have to do is see here what weight is what for we have selected this one then four minus four is what zero then we will go to the column having weight zero here what we have zero three plus zero or this one maximum of this new value or the value just above this sell a value above the cell is what to why we have taken this value if we have selected this one then the profit would be three plus zero if we will not select this one the only remaining item is what three then you have to select this item and the way profit of this item is what to and here what what it has written that is to the best of three and two is what maximum of this one is what three then we will write here what three okay now next is here we have total weight is what five if and available items is worth four and three now you have to select maximum of C if we select this item we are selecting this four we can select this four because total weight is what we have five then if we have selected this item then profit would be what 3 plus remaining weight is what 5 minus 4 that is one go to the above sell and go to the column having weight one hey what is the value zero three plus zero or the value just above this sell what the value is what is to maximum of three and two is what three will select we will write here what three see if you will not select this one then only remaining item is what tray then you have to select this three and the weight the profit is what to so this one is written here is two so here we have taken this word the value from the about it that is three same with this one suppose we have selected this one their profit is what three plus what is the value of this wait six six minus four is what to go to the above row and then you have to go to the column having wait - 6 - 4 - that is 0-3 mine 3 plus 0 or you will take this one the value in the bow sell 3 + 2 maximum is what 3 okay now for this cell we have now in available set we have 2 items having made three and four if we select this 4 we have to find out the maximum if we select this 4 then the profit is what 3 plus you have selected this 4 and the total weight is what 7 the remaining weight is what 7 minus 4 that is 3 okay now go to the upper row and find out the column having grade 3 now see here what is the profit that is to the 3 + 2 + maximum of this one or what is the value in the upper cell that is to the maximum of 5 and 2 what is the maximum that is 5 it will take care what fight sorry for this one same case suppose we have selected this 4 then you have to find out maximum move if you selected this 4 then profit is what 3 3 + we have selected this 4 but the weight is what total weight is what 8 the remaining weight is what 8 - 4 that is 4 now go to the upper row and find out the column having weight for hair profit is what 2 3 + 2 and in upper row we have what two things know this one is what 5 now I value is increased by 1 now we have those three items in our available said now next item is what having made five simple trick is what what from 0 to 4 you will copy the value from the upper cell 0 0 2 and three from zero to four because here we have what five okay now at five you have to find out the best ace now you can select either you can select this 5 4 you will not select this 5 if we select this 5 then profit would be what for this one profit is what 4 4 + find out the remaining weight total weight is 5 we have selected 5 remaining is what 5 - 5 0 go to the Perot and find out the column having weight to 0 here what we have value or you can say the profit is 0 and what is the value in the upper sell happy happy fill car there then you have to find out the value just in the upper cell that is 3 out of 4 + 3 which is which is maximum that is 4 here also maximum of suppose we have selected this 5 now profit is what 4 plus we have to deliberate 6 we have selected 5 remaining weight is about 6 minus 5 that is 1 only go to the upper low and go to the column having weight 1 here what we have value 0 4 + 0 in the upper row we have 3 out of 4 & 3 which one is maximum that is 4 now in the case of 7 you have to find out same case maximum if you select this 5 profit is worth 4 plus we have selected 5 and the total weight is 7 remaining weight we have waters 7 minus 5 that is to go to the Perot and go to the column having bit to hear what we have 0 4 + 0 in the upper row row we have what 5 now 2 4 & 5 which one is maximum 5 will select what 5 okay now next here same case maximum of we have selected suppose this 5 having item having weight 5 profit of this as what 4 4 + total weight is 8 remaining weight is 8 minus 5 that is 3 go to the upper row go to the column having weight 3 here what we have value - 4 + 2 in the upper robot we have 5 out of 6 & 5 the maximum is 6 okay now for the astro we have now I values increased by one we have now four items in our available set three four five and six now I got paid is what six then from zero to five you will copy the value from the a person as a piece now for six two cases either you will select this six or you will not select this one okay you have to find out the best case if we select this sixth one suppose we have select this one six then wait is what sorry the profit is what one okay plus now remaining weight is what total weight is 6 6 minus X zero go to the upper row here what we have in the 0th column having zero value is what profit is what 0 1 plus 0 in the upper robot we have 4 out of 1 and for which one is maximum for here in this case maximum move suppose we have selected 6 same profit is 1 plus 7 minus 6 that is 1 in the upper row go to the column having the 8 1 0 1 plus 0 in upper over we have five out of 1 & 5 which one is maximum 5 here also you have to find out maximum of 1 plus 8 minus 6 that is 2 in the upper row in the column having weighed 2 we have what profit 0 in the upper sell what we have 6 out of one and second which one is maximum that is 6 okay now here the answer would be in the last row and last column 6 the maximum profit would be what 6 okay the formula is C I'm just writing the formula here you can check out that formula how you will fill out a particular cell what is the formula suppose the name of this matrix is I am taking m M of I and W particular cell suppose this cell this cell would be mfin WI value is what this 3 + W value for this cell is what this 3 three and three how you will fill out this value maximum of Mo I minus one for W her mo hi minus 1 this w minus W of I plus profit of that item fine you can verify this formula also suppose we are taking any example of this one this Phi this the same for this one this one suppose value Phi is what for value of W is what seven now maximum of M I minus 1 that is 3 W is what 7 okay comma M hi minus 1 3 W is what 7 7 minus weight of I I is what for weight of I is what 6 7 minus 6 plus profit of I high value is what for here profit of this one is what 1 1 here what we have M of 3 and 7 I value is 3 here W value is 7 means this cell value is what 5 comma 7 minus 6 that is one M of 3 1 I value is 3 here what we have W value M here what we have 0 plus this one out of five and one which one is maximum that is 5 well how many be happy careful quwata fine so this is the formula to fill out this table ok now you have to find out that if you will select that item owed you will not select that item club 0 and 1 then how will find out that thing we have what four items suppose X I am writing here you I will write 0 1 you will select me there you will say legacy that item and you will not select that item now what is the processor now over here over here you will get the answer the maximum profit would be what 6 okay now pointer is at this place and what you have to do is just check out the above sell here also what we have 6 ok then we will not select this item in the above and also you have the same value okay now pointer is here now go to the upper row here we have 6 no we don't have sex because you have a fire you have a six-way in that case we will select this item that is well select a weight item having bit 500 Konoha marry past the last one the last one we I will write what one Ori applicants akka wait six wait six yep not a third one okay now what you have to do is I am need a select key curlier take it now profit is what six we have selected this one and profit of this is what for the remaining profit is what 6 minus 4 that is 2 now check out in the above in the above row do we have to yes we have this to fine pointer is here now now check out in the upper row do we have to yes we have to now pointer would be in the upper row now in the in the upper row go to the upper row is there any - no we don't have any - then we will select this one this item having made three that is this item one but we haven't select this item having date for fine we have selected this item now after selecting this item the profit is what - remaining profit on a bass guitar - and the profit hamari passing our care to remaining is what zero in the borrow we have zero but we have reached towards the 0th row so that's it one zero zero and one will select this item and this item five plus three we can select these item because total weight is what eight that is fine because maximum way it should be what that weight of item should be what less than or equal to W and the second approach to find out which item we have selected is C we are we have find out the result or you can say the maximum profit in the last row and last column that is six now what you have to do is one pointer is here this place now this pointer will be move upward here what we have six okay now again upward direction now here the value is about five the value has been changed he have a facing up a six over here in that case we will select this weight that is five and here what we have one or is commonly selected Nakia six who here would we have this one is x3 is what 0 okay x1 x2 x3 and x4 okay now next we have selected this one now what you have to do is the way it is what it we have selected this way that is five remaining way it would be 8 minus 5 that is 3 fine now go to the upper row and go to the column having weight 3 say many weight is 3 now you have to go to this column this 3 the value is what to go to the upper row the value is what to will not select this one will not select this for go to the upper the value has been changed so we'll select this 3 here 3 methyl of one for common a select nature that is zero fine is common a select earlier thicken now what you have to do is wait is what corresponding to this cell is what three we have selected this item wait is worth 3 3 minus 3 that is zero now go to the upper row and go to the column having weight 0 that is 0 we have raised to the initial point and this is the answer so you can find out the answer using this weight also and by the by looking the profit also okay so this is the 0 and knapsack problem in next video I will discuss that next one that fractional knapsack problem till then bye bye take care

Channel: Jenny's lectures CS/IT NET&JRF

Views: 264,797

Rating: 4.8300285 out of 5

Keywords: knapsack problem, knapsack algorithm, fractional knapsack problem, 0 1 knapsack problem, dynamic programming, jayanti khatri, jenny's lecture, data structure, data structures and algorithms, ugc net computer science, algorithms, ugc net syllabus, knapsack problem using dynamic programming, dynamic programming examples, algorithm in data structure, advanced data structures, jennys lectures, GATE computer science preparation, study material, engineering, c programming, it, cse

Id: PfkBS9qIMRE

Length: 27min 30sec (1650 seconds)

Published: Wed Mar 06 2019