Fractional Knapsack Problem using Greedy Method | Example | Data structures and algorithms

hi guys in this video I'm going to discuss with you fractional knapsack problem we have already discussed zero-one knapsack problem if you want to check out that video then I'll provide you with the link in the description box okay so here we are given some objects seven objects with their weights and profits and total weight is given what 15 kg suppose I am taking the weight in kgs total items have 17 paces so much after we have one bag ok having date 15 kg or you can see one container having capacity 15 kg okay now you have to select item such that you will get the maximum profit we cannot select all the items because if you total the weight of all the items then it would be greater than 15 so we cannot select all the items okay because extreme capacity is 15 kg of this bag now how you select the item so that you will get the maximum profit so there are three approaches you can say that will select the item first which is having maximum profit see the maximum profit is 15 so will select this item then we will select this item then will select this item like this okay or maybe second approach is what we will select items having minimum rate so that we can we can select more and more items minimum weight like this one we can select this one then this one then this one then three then three then four and five like this second approach third approach is what maybe I can say that I will find out the ratio of profit by weight and then I will select the item having the maximum profit by weight ratio see the profit of this item is 15 you can say maximum profit but this profit is for 5 kgs it is not for 1 kg if you will find out the profit for 1 kg then profit would be what 15 by 5 that is 3 for 1 kg it is 3 and here for 1 kg we have 5 so this is this is good choice rather than this one okay so the best process best approach is to find out the ratio profit by weight and then select the items having that maximum profit by weight ratio and discuss we knew all the three approaches and then we will compare all the three approaches so first one is you will select the items according to their maximum profit second one is according to minimum weight and third one is according to the maximum profit by weight ratio okay first approach okay the first approach is select the items according to their maximum profit okay this is the table now check out which item is having maximum profit that is 15 then we will select this object object name is what 3 profit is what 15 weight is what 5 remaining weight is what see total weight is 15 15 minus 5 we have selected this item the remaining is what 10 now next is maximum profit is what after this 15 we are done with this 15 10 object is to profit is what 10 weight is what three remaining weight is about 10 minus 3 that is 7 now we are done with this one also now next is what this 9 object is 6 profit is 9 weight is what 3 remaining is 7 minus 3 that is 4 we are done with this one now next is eight object is what five profit is 8 weight is what one remaining is 4 minus 1 that is 3 we are done with this one next maximum I do is what 7 object is for profit as 7 way it is see here where it is what for but we have one remaining weight that is 3 so we cannot select the complete object we cannot pick the complete object as the name suggest wreck as the name suggests that is frictional so we have to select friction of this object see this object is divisible ok so we have four kg of Apple then you will select only three kg of apple because the remaining capacity is what only three so out of four the weight you will select is what three the profit would be according to this three because we have selected this 3 and this 7 is profit is what 4 4 kg so you have to find out the profit for 3 kg and that profit would be 7 into we have selected only 3 out of 4 3 by 4 that would be 21 by 4 and that would be 5 point 2 5 now remaining weight is what 3 we have selected 3 that is 0 yup is zero energy in the last ok now check out what is the total profit here the total profit is forty seven point two five I am writing here forty seven point two five in the first method now I will discuss the second method choose the item according to their minimum weight okay now second approaches we have to select items according to their minimum weight find out minimum weight is what one and one so you can select this one or this one will select suppose this one first one object is what one profit is five weight is one remaining weight is what total is 15 15 minus one that is 14 next minimum is this one object is five profit 8 weight is one remaining 14 minus one that is 13 we are done with this one and this one next is 2 object 7 profit is for weight is to 13 minus 2 that is 11 we're done with this one next is 3 and 3 so you can select this either this 2 or either this 6 we are selecting suppose to profit 10 remain weight is what 3 remaining is 11 minus 3 that is 8 we are done with this one next three object six nine three remaining eight minus three that is five we are done with this one now next minimum is what this for object is for profit seven we have selected this four remaining is 5 minus 4 that is 1 now we are done with this four also now next is what this one five object is 3 now remaining weight is what one only and the total weight is what 5 so we cannot select the complete object your select you will select the friction of this object that is 1 by v you will select only one kg out of 5 kg and this profit is what for 5 kg and for 1 kg the profit would be 15 into 1 by 5 that is 3 remaining 1 minus 1 that does 0 okay now finally total weight is what 0 we cannot select any more item okay now find out the total profit the total would be what the total profit would be for the 6 for the second approach it would be 46 now I'll discuss the third one we will find out the ratio of this profit by weight and then we'll select the maximum profit by weight ratio okay the third approach is what you have to find out the profit by weight ratio okay for 1 kg you will find out the profit see profit is 5 it is for 1 kg that is 5 P by W here profit is what 10 but it's it is what for 3 kg for 1 kg what is the profit 10 by 3 that is 3 point 3 same 15 by 5 3 7 by 4 1 point 7 5 8 by 1 8 9 by 3 and 4 by 2 we have find out profit by weight ratio now I will select the items according to the maximum profit by weight ratio find out the ratio maximum is what this 1 8 okay now we will select this object of is what five profit is what eight weight is what one remaining is what 15 minus one that is for you we are done with this object five now next maximum ratio is out of eight we have five select this item one five profit weight is 114 minus one remaining is what thirty we are done with this one now next is what eight five then we have three point three next maximum is object is what - profit ten way it is what this three remaining is 13 minus 3 that is 10 we have okay next we have selected of all this 2 also next ratio is 3 and 3 so you can select either this one or this one we're selecting suppose this 3 object is 3 profit is 15 weight is about five remaining is 10 minus 5 that is 5 next we'll select this 6 profit 9 weight is worth three remaining is 5 minus 3 letters - we are done with this one now next ratio next remaining object as 4 and 7 2 and 1.75 so maximum is what this 1 2 will select object 7 okay now find out the weight that is 2 remaining is also 2 then we can select the complete object okay they take this very profit as for weight is what 2 remaining 2 minus 2 that is C now find out the total of these 1 the total would be what okay so the total profit would be 51 foot when we are following the third approach then profit is what 51 so the maximum profit is what that is 51 we have got this profit in the third approach so this approach is the best one okay as a key question either you have to solve this question according to this approach you have to first find out profit why ratio then you'll select the maximum profit by weight ratio item okay then you will get the maximum profit so this is what the frictional knapsack problem and this is known as greedy method so please keep in mind one thing in frictional knapsack problem you'll find out the optimized result when you apply greedy method but in zero-one knapsack problem it is better to use dynamic programming for fractional greedy method is good and 4:01 dynamic programming method is good okay so I'll see you in the next video till then bye-bye take care

Channel: Jenny's Lectures CS IT

Views: 420,418

Keywords: dynamic programming, 0 1 knapsack problem, jayanti khatri, jenny's lecture, ugc net computer science, problem, lattice, knapsack meaning, fractional knapsack problem, knapsack algorithm, greedy knapsack algorithm, c programming, net and jrf, data structure, data structures and algorithms, data structures in java, algorithms, DAA, GATE computer science, ugc net computer science and applications, study material, dsa notes, data structures and algorithms full course

Id: xZfmHVi7FMg

Length: 11min 56sec (716 seconds)

Published: Wed Mar 06 2019