the problem that we will be solving today is fractional knapsack so what is the problem stating stating that you will be given n items and every item will have a value will have a weight to it so basically it'll be given n pairs along with this'll also be given the weight so what does this particular weight signify you have a bag and that bag can hold a maximum weight of 90 not Beyond it now your task is to pick up items you can pick in any order you can pick in any order imagine you start with picking the first item that means you're taking a value of 100 first one is the value and that is uh taking a weight of 20 so if your bag is already taking a weight of 20 can I say that you can only take 70 more weight not not more than that yes I can I can pick up this one which means I'm adding a value of 60 and it's taking a weight of 10 which means the weight can be reduced to 60 perfect after this I can pick up this one which means it's a 100 value it's a 100 value but the weight is 50 which means I'm left off with 10 weight that I can take maybe I can pick up this one but can I pick up this one is the question I cannot pick up this one why because the remaining weight that my bag can take is 10 and this is taking a weight of 50 this is taking a weight of 50 so this cannot be taken but over here the question is different it is a fractional lapack it's not necessary that you take the entire item you can also take a fraction of it you can also take a fraction of it so over here I'm saying 508 means 200 value and I just have 10 weight remaining so can I say that one weight means 200 by 50 correct and 10 weight means because 10 ising 200 by 50 into 10 So Gone Gone 540 so maybe I can just pick up 10 weight and that 10 weight will give me 40 Value then underst it so what will be the total value that I have picked up that's 100 that's another 60 that's another 100 that's another 40 and that sums up to I think 300 now the question is asking you to maximize the total value that you can take in the bag yes you have to maximize this so this was a pattern in which you can pick I started picking the first element then the second then the third then the fourth again I have stated that it can be in any order can try out every possible combin combination your task is to maximize the total value so what I will do is I'll try out other examples since I know the answer I'll try out the possible answer configuration so I have a weight of 90 what I will do is I'll pick up this one so that is a value of 100 and a weight of 10 so have left with 70 then I'll pick up this one 60 comma 10 so 10 gone I'm left off with 60 then I'll pick up this one which is 200 comma 50 so 50 gone left with 10 after that this is a 50 weight but I'm left over with 10 so what I'll do is I'll pick up a fraction 50 is giving me 100 1 will give me 100 by 50 10 will give me 100x 50 into 10 which means 20 20 value so I'll take a 20 value and a weight of 10 done and dusted and if you add them up it's 100 plus 200 300 360 380 so the value that you get is 380 you can drout all of the possible configuration and this is the maximum value that you can get you cannot go beyond this and this is what you'll have to return you don't have to return which uh items you picked up just uh returning the value value will do but when I solve this problem even if the interviewer will even if the interviewer does ask you which items did you pick up you can see that as well okay I hope uh you have got the question right so how do I solve this how do I solve this is a big question now the first thing that comes to your brain is okay you have a weight of 90 you want to maximize value why don't you pick up the value 200 at first because pick up the maximum that that is something that will come to your brain right then I'll just give you a small example imagine I change this to 90 so this is typically 200 comma 90 if you're thinking I'm going to pick up the maximum value then what will happen is when you pick up this 200 comma 90 you're done you cannot pick up anything else anything else and your total value will be 200 I can actually do better I can actually do better if I decide that okay I'm going to pick up this this this that's going to be 100 comma 20 60 comma 10 100 comma 50 we still in limit we're still in limit and we can pick some of this as well right this is 160 100 this is already 260 which is greater so it is not necessary it is not necessary that you always pick up the maximum value correct okay then how do I pick up that's a big question I have a weight of I have a weight of 90 that I'll I have to carry right what if I say I'm going to pick up the item which gives me the maximum value for one weight for one weight unit mathematics okay makes sense so can I say this gives me five y because I'm getting 20 like 20 weight is giving me a 100 value correct so one weight will give me 100 by 20 which is five so one weight if I'm taking one weight that's that gives me a five value okay over here can I say if I take one weight that gives me six value over here can I say 100 by 50 one weight gives me two value over here one weight gives me four value so thinking greedy because I'm over here to maximize my total value thinking greedily what will I do I'll be like take this one dude this gives me the maximum so I'll go ahead and say okay 60 comma 10 is what I'll take perect and that will reduce the weight to remaining weight to 80 perfect taken what after this I'll be like I'll take this this gives me per uh weight value more take it 100 comma 20 so you reduce this to 60 now perfect this is also taken after the switch one this one so you take 200 comma 50 again uh you can take the entire thing because this is greater than the remaining weight after this you leftt off with 10 now when you go to pick up the next one what happens is you have a 50 weight but you're left over with 10 now this is where you say that okay I don't have a lot of capacity remaining so I'll pick up a fraction of you so I'll be like okay 50 means 100 50 weight is giving me 100 one weight will give me 100 by 50 and I just have 10 remaining so 100 by 50 into 10 that's going to be 20 so I'll just pick up 20 value I'll pick up 20 value that's a 10 we I'll go off I'll go off and remember the like this might be 120 might be possible might be 120 then the the answer will be in fraction the answer will be in decimal points so you have to use double or float while you Cod done if I add this up the total value will be 3 380 and that is what you will be returning how do I solve this you did C right so what I'll do is I'll sort the array yes I'll sort the array according to the fraction weight like according to the per weight what is per weight it's very simple value per weight for one weight that's value per total weight rate okay according to this I'll sort if I sort it according to this in the reverse order it's very important in the reverse order if I do it I'll get 60 comma 10 at first right then I'll get 100 comma 20 then I'll get 200 comma 50 and then I'll get 100a 15 now if there are same values for an example if this was also five it doesn't matter which one you take it first because eventually the value per weight is same so it doesn't matter you can take either of them done so I have the sorted one you have to write a comparator you have to write a custom comparator in case you don't know how to write a custom comparator I have a C++ STL lecture right you can go back uh to that lecture and I've have taught you how to write a custom comparator you'll have to write it over here because the custom comparator will be value by weight and in descending order done and dusted now what you will do is you'll be like okay what is my weight remaining 90 so you'll take a total value which is zero let's start off so you start off with the first one maybe I can use some different color yeah I can use some different color so I'm standing at the first one can I pick up this entirely I have a 10 wait I can pick up this entirely so my value will be added by 60 and I'll pick up this entirely and if I pick up this entirely the 90 gets reduced to 80 next I'll move to the next can I pick up this entirely I can so the total value gets added 160 and the weight reduces to 60 can I pick up this entirely yes I can so this gets added 360 so you added the value the value is 360 the weight will reduce so it will be 10 now and after that you can move to the next one can you pick up the entire item the answer is no because it weighs 50 and you only have 10 left so you cannot pick up the entire item so what will you do you'll be like okay I'll pick up a fraction so one weight will be 100 by 50 which is two one weight is two and you're left off it 10 so what you can do is you can multiply 10 you'll get 20 value addition you can add 20 it will make 380 and this can be zero and the moment this is zero you can break off yes you can break off that underst if this is zero that means even if there were elements after this you don't care you can just break off so at any moment when the weight is lesser than the remaining one you just take whatever weight is remaining which is 10 over here and you break off this is how you can easily do it so I'll be writing down the pseudo code in case case you want the language specific code you can find them below so I'll be writing down the function function will be taking the item are and the W and the function will be returning the total value and the total value can be fractional so I'll be returning double what is item item is nothing but an object and this particular object can have a value and a weight again depending on the programming language you're using you're using C++ it can be a structor class if we're using Java this can be a class right so what is the first step the first step is to sort this particular item array correct so I'll be sorting this particular item array according to an comparator now this will be a custom comparator if you don't know how to write a custom comparator you can pause this video go back to my C++ STL video or the Java video right and you can and learn how to write a custom comparator so I'll be writing a custom comparator that sorts it according to value by weight and in descending order got okay now what is the next step the next step is to iterate it'll be keeping a total value which is initially zero and I'll be iterating so let's iterate so I'll be iterating from zero till the the last what is the first thing that I'll do I'll be like okay if in the array of I if this particular weight I'll take the weight from that uh index I'll say hey if this is smaller than the capacity W I can pick up this entirely I can pick up this entirely so it be like total Value Plus equal to array of I do value quite simple and at the same time W will be W minus array of I do weight perfect but what if it is not what if the weight is greater than equal to the capacity that means I'll go to the else and if I go to the else what will happen I'll be like okay I have to compute the per weight and the per weight will be array of I dot value by array of I dot weight please make sure use double because on dividing the values will be in fraction multiplied with the remaining weight and the remaining weight will be W right and this is what you will add to total value and once this is added you'll be like like okay maybe now we can break free and that's it and once you have done this what you will be returning is the total Val and that's done and the function is completed just make sure that this is double also make sure this is typ casted again you can find the code below these things are very very important otherwise you will be getting wrong answers and once you have done this that is done and dusted I'll be writing down the custom comparator don't worry what is this custom comparator it's typically a Boolean function so let's try to write down the custom comparator so it be like okay bullan competitor and what is the array having the array is having items so I'll be like item maybe uh I can call it as value one and item value to because this is how you write a custom comparator and what am I doing I'm like okay if I have to compare it with value per weight value per weight so I'm like value 1 dot value divided by value 1 do weight if this is greater than equal to Value 1 sorry value two dot value by value two dot weight this means this means it is correct it is in the correct order when you write a custom comparator value one is always before value two and it is asking am I maintaining the order and you're right you're like okay if the per weight is greater than the value to weight you're correct because I'm maintaining a descending order so you'll be like like you are correct and you can return a true or else you will be returning a false that's it that is your custom comparator again go back to the C++ STL or Java in one short video you will understand this so this is done now what is the time complexity can I say this will be taking n logarithmic of I can and can I say this will be taking a b go of n at the worst possible case there the time complexity is n+ n log n and that is the time complexity and what is the space complexity beo of one yes I did uh distort the array but that will not be computed in this particular case because this is the only way in which you can solve this particular problem or you'll have to take an external container to store all the elements now what is greedy in this you know what is greedy right you sorted it you sorted it according to the value per weight you sorted it according to the value per weight why because you want it to maximize the total value and this is where 3D algorithm comes in it's not a specific algorithm it's a very generic way to solve a problem right so yeah this will be it for this one so if you're still now watching and if you've understood everything please please do consider giving us a like and if you're new to our channel do consider subscribing to us as well with this I'll wrapping up this video experience some other video tillen golden I will