1 00:00:00,140 --> 00:00:01,250 Welcome back. 2 00:00:01,250 --> 00:00:07,730 In the previous videos we have got ourselves introduced to the greedy algorithmic approach. 3 00:00:07,760 --> 00:00:11,810 Now let's get started with a few interesting coding interview questions. 4 00:00:11,810 --> 00:00:17,510 So over here we have a beautiful question which is the fractional knapsack problem. 5 00:00:17,510 --> 00:00:24,080 Previously under dynamic programming, we have already discussed the zero one knapsack problem and the 6 00:00:24,080 --> 00:00:25,760 unbounded knapsack problem. 7 00:00:25,760 --> 00:00:27,770 So let's get started with this question. 8 00:00:27,770 --> 00:00:28,370 Over here. 9 00:00:28,370 --> 00:00:36,830 The question reads determine how to optimally fill a knapsack with a capacity of w kilograms, using 10 00:00:36,830 --> 00:00:43,400 a list of n items where each item is represented by a pair profit comma weight. 11 00:00:43,400 --> 00:00:50,690 In the fractional knapsack problem, you can take fractions of items to maximize the total profit in 12 00:00:50,690 --> 00:00:56,900 the knapsack, and then it's mentioned n will be greater than equal to one, which means that you will 13 00:00:56,900 --> 00:00:59,540 not be given an array which has nothing in it. 14 00:00:59,540 --> 00:01:01,790 Okay, so that's mentioned in the question. 15 00:01:01,790 --> 00:01:05,720 And therefore we don't need to account for it explicitly in our solution. 16 00:01:05,720 --> 00:01:08,540 So that's all that this line over here gives. 17 00:01:08,540 --> 00:01:10,670 Now we are also given an example. 18 00:01:10,670 --> 00:01:14,360 So let's take a look at the example to thoroughly understand this question. 19 00:01:14,360 --> 00:01:16,340 So we are given this array over here. 20 00:01:16,340 --> 00:01:18,950 And we can see that it has three elements okay. 21 00:01:18,950 --> 00:01:20,420 So this is item one. 22 00:01:20,420 --> 00:01:23,150 This is item two and this is item three. 23 00:01:23,150 --> 00:01:28,730 And we know that each of these pairs represent the profit and the weight of the item. 24 00:01:28,730 --> 00:01:36,410 So item one if added to the knapsack would increase the profit by 70 and the weight by ten. 25 00:01:36,410 --> 00:01:42,230 And also notice in the question it says that you can take fractions of items okay. 26 00:01:42,230 --> 00:01:47,630 So if you take the whole item one then the profit added to the knapsack would be 70. 27 00:01:47,630 --> 00:01:51,800 And if you add, let's say one tenth of this item, okay. 28 00:01:51,800 --> 00:01:57,830 If you add one tenth of this item, then the profit added to the knapsack also would be one tenth of 29 00:01:57,830 --> 00:02:00,290 70, which is equal to seven. 30 00:02:00,290 --> 00:02:02,300 So this is just to understand the question. 31 00:02:02,300 --> 00:02:04,490 So again we have these three items. 32 00:02:04,490 --> 00:02:13,460 And in the first scenario over here it's given that w is equal to 25 which means that the knapsack has 33 00:02:13,460 --> 00:02:15,740 a capacity of 25kg. 34 00:02:15,740 --> 00:02:20,750 And the expected output in this case is equal to 145. 35 00:02:20,750 --> 00:02:24,680 And for this you can take the whole of item one okay. 36 00:02:24,680 --> 00:02:26,990 So that would add ten kilograms. 37 00:02:26,990 --> 00:02:31,880 And you can take half of item three which would add 15kg. 38 00:02:31,880 --> 00:02:36,140 And the total in this case would be ten plus 15 which is 25. 39 00:02:36,140 --> 00:02:40,730 And when you add the whole of item one you are increasing the profit by 70. 40 00:02:40,730 --> 00:02:47,210 And when you're taking only half of item three, you are increasing the profit by half of 150, which 41 00:02:47,210 --> 00:02:51,710 is 75 and 70 plus 75 gives us 145. 42 00:02:51,710 --> 00:02:52,100 Okay. 43 00:02:52,100 --> 00:02:55,550 And again, this is the best way in which the knapsack can be filled. 44 00:02:55,550 --> 00:03:00,140 Like for example, you could add ten over here and then you're left with 15. 45 00:03:00,140 --> 00:03:02,840 And you could take 15 from item two as well. 46 00:03:02,840 --> 00:03:05,180 And if you do that what would be the profit? 47 00:03:05,180 --> 00:03:12,110 The profit would be 70 plus 15 out of 20 into 90 okay. 48 00:03:12,110 --> 00:03:14,360 And this would simplify to. 49 00:03:14,950 --> 00:03:22,840 15 into 4.5 plus 70, which is equal to 70 plus 67.5 okay. 50 00:03:22,840 --> 00:03:26,890 And this definitely is lower than 70 plus 75. 51 00:03:26,890 --> 00:03:29,260 So again that's the example given to us. 52 00:03:29,260 --> 00:03:31,240 And we have one more example. 53 00:03:31,240 --> 00:03:38,920 If the capacity of the knapsack was equal to 45 kilogram, then the expected output would be 240 2.5, 54 00:03:38,920 --> 00:03:43,870 which can be achieved by taking ten kilograms of item one. 55 00:03:43,870 --> 00:03:48,820 And then you have five kilograms of item two and 30kg of item three. 56 00:03:48,820 --> 00:03:49,210 Okay. 57 00:03:49,210 --> 00:03:53,800 And because you're taking the whole of item one, the profit increases by 70. 58 00:03:53,830 --> 00:03:56,200 You're taking the whole of item three. 59 00:03:56,200 --> 00:03:58,600 So the profit increases by 150. 60 00:03:58,600 --> 00:04:02,470 And you're taking five kilogram of item two. 61 00:04:02,470 --> 00:04:08,410 And therefore the profit would increase by 90 into five by 20. 62 00:04:08,410 --> 00:04:08,920 Okay. 63 00:04:08,920 --> 00:04:11,020 And five by 20 is one by four. 64 00:04:11,020 --> 00:04:13,630 So that's how you get 90 by four over here. 65 00:04:13,630 --> 00:04:20,290 And when you add all of these up you get 240 2.5, which is the maximum profit or the maximum value 66 00:04:20,290 --> 00:04:25,150 that you can add to the knapsack when the input array is this array over here. 67 00:04:25,270 --> 00:04:25,780 Okay. 68 00:04:25,780 --> 00:04:27,490 So this is the question over here. 69 00:04:27,490 --> 00:04:32,830 Again to summarize you're given a sack and the maximum weight capacity of the sack is mentioned. 70 00:04:32,830 --> 00:04:38,470 And you have to pick items from the array which is given over here and add them into the knapsack. 71 00:04:38,470 --> 00:04:42,310 And the aim is to maximize the profit in the knapsack. 72 00:04:42,310 --> 00:04:48,490 And the criteria given in the question is that you can take part of an item or a fraction of an item, 73 00:04:48,490 --> 00:04:51,160 and you can add a fraction of an item to the sack. 74 00:04:51,160 --> 00:04:51,940 So that's allowed. 75 00:04:51,940 --> 00:04:54,730 So this is the fractional knapsack problem. 76 00:04:54,730 --> 00:04:57,340 And in the next video let's get started. 77 00:04:57,340 --> 00:05:01,450 And let's try to think about the approach that we can take to solve this question.