1
00:00:00,110 --> 00:00:01,010
Welcome back.

2
00:00:01,010 --> 00:00:05,630
Let's now implement the code for the approach that we have discussed in the previous video.

3
00:00:05,630 --> 00:00:06,020
Okay.

4
00:00:06,020 --> 00:00:09,560
So we're given this function over here fractional knapsack.

5
00:00:09,560 --> 00:00:12,980
And we are given the weight capacity of the knapsack.

6
00:00:12,980 --> 00:00:15,290
And we are also given this array over here.

7
00:00:15,290 --> 00:00:21,350
And it's mentioned in the question that every element in this array will be an array by itself, which

8
00:00:21,350 --> 00:00:27,530
will have two elements of which the first represents the profit and the second represents the weight

9
00:00:27,530 --> 00:00:29,210
of that particular item.

10
00:00:29,210 --> 00:00:29,630
Okay.

11
00:00:29,630 --> 00:00:35,060
And we are also given n, which is the number of elements or the size of this array over here.

12
00:00:35,060 --> 00:00:41,990
Now to start with we are going to sort this array over here by the ratio of profit by weight of every

13
00:00:41,990 --> 00:00:43,130
element in this array.

14
00:00:43,130 --> 00:00:45,710
And we are going to do it in descending order.

15
00:00:45,710 --> 00:00:47,270
So let's go ahead and do that.

16
00:00:47,270 --> 00:00:49,190
So I can say r dot sort.

17
00:00:49,930 --> 00:00:51,880
And I have a comma B over here.

18
00:00:51,880 --> 00:00:59,110
And the criteria is that we're going to sorted in descending order by the ratio of profit by weight

19
00:00:59,110 --> 00:00:59,560
okay.

20
00:01:00,100 --> 00:01:01,540
So let's implement that.

21
00:01:01,540 --> 00:01:10,360
So I have b at zero divided by b at one minus a at zero divided by a at one okay.

22
00:01:10,360 --> 00:01:15,250
And again remember in the question is given that every element in this array will have this structure

23
00:01:15,250 --> 00:01:19,930
where the first element is the profit and the second element is the weight.

24
00:01:20,530 --> 00:01:20,800
Okay.

25
00:01:20,800 --> 00:01:25,000
So b at zero would give the profit, B at one would give the weight.

26
00:01:25,000 --> 00:01:29,140
Similarly, a at zero would represent profit and a at one represents weight.

27
00:01:29,140 --> 00:01:35,050
So we are sorting the array in descending order by the profit by weight ratio.

28
00:01:35,050 --> 00:01:36,610
So that's what we're doing over here.

29
00:01:36,610 --> 00:01:44,740
And after this let's say remaining weight is equal to W because as of now nothing has been added to

30
00:01:44,740 --> 00:01:45,490
the knapsack.

31
00:01:45,490 --> 00:01:50,710
And because nothing has been added to the knapsack, the value in the knapsack is also zero.

32
00:01:50,710 --> 00:01:56,440
Now what we will do is we will just go through each element in the array, okay?

33
00:01:56,440 --> 00:02:02,680
And because we have already sorted the array by the profit by weight ratio in descending order, we

34
00:02:02,680 --> 00:02:05,380
would just need to take the element that we are getting.

35
00:02:05,380 --> 00:02:09,310
So we start at index zero and go up to index n minus one.

36
00:02:09,310 --> 00:02:12,730
And we keep adding as much as possible of every item.

37
00:02:12,730 --> 00:02:13,180
Okay.

38
00:02:13,180 --> 00:02:20,020
And before we decide whether we can add a particular element or sum of a particular element to the knapsack,

39
00:02:20,020 --> 00:02:25,510
we have to check if the remaining weight at that particular instance is equal to zero, because if that

40
00:02:25,510 --> 00:02:30,250
is the case, then we will not be able to add more items, and we would just have to break out of this

41
00:02:30,250 --> 00:02:30,790
for loop.

42
00:02:30,790 --> 00:02:37,450
But if that is not the case, then we first have to decide the weight of this particular item that can

43
00:02:37,450 --> 00:02:38,680
be added to the knapsack.

44
00:02:38,680 --> 00:02:45,760
And that would be math dot min, or the minimum between the remaining weight and the weight of this

45
00:02:45,760 --> 00:02:47,710
particular item which is given to us.

46
00:02:47,710 --> 00:02:50,980
Okay, that would be our at I at one.

47
00:02:51,610 --> 00:02:53,290
Again, let me quickly explain this.

48
00:02:53,290 --> 00:02:57,970
Now let's say the remaining weight that can be added is two units.

49
00:02:57,970 --> 00:03:02,050
And let's say for a particular item we are given just one unit okay.

50
00:03:02,050 --> 00:03:03,220
So the weight is just one.

51
00:03:03,220 --> 00:03:08,740
So in that case, even though the remaining weight that can be added to the knapsack is two, because

52
00:03:08,740 --> 00:03:13,060
we don't have two units of this particular item, we would just be able to add only one.

53
00:03:13,060 --> 00:03:15,910
But on the other hand, if this over here would be three.

54
00:03:15,910 --> 00:03:16,360
Okay.

55
00:03:16,360 --> 00:03:20,680
Now, because the remaining weight that can be added is just two units.

56
00:03:20,680 --> 00:03:26,710
So that's why we will not be able to add three units, but rather only two units to the knapsack.

57
00:03:26,710 --> 00:03:32,170
So that's why the weight that can be added to the knapsack at this point would be the minimum between

58
00:03:32,170 --> 00:03:35,800
the remaining weight and the weight of the given item.

59
00:03:35,800 --> 00:03:36,220
Okay.

60
00:03:36,220 --> 00:03:41,650
And after we have decided the weight of the item that's going to be added to the knapsack, we are going

61
00:03:41,650 --> 00:03:44,470
to reduce the remaining weight by that amount.

62
00:03:44,470 --> 00:03:44,680
Okay.

63
00:03:44,680 --> 00:03:47,650
So we can say remaining weight minus is equal to weight.

64
00:03:47,650 --> 00:03:53,800
And all that now remains is to increment the value in the knapsack by the value of the item that we

65
00:03:53,800 --> 00:03:55,420
have added to the knapsack, okay.

66
00:03:55,420 --> 00:04:02,200
And therefore value is going to be value plus the value of the item that has been added to the knapsack.

67
00:04:02,200 --> 00:04:07,870
And to find the value of that, we would just have to take the value of the total item which is given

68
00:04:07,870 --> 00:04:12,550
to us, and then divide it by the weight of that particular item which we have.

69
00:04:12,550 --> 00:04:16,750
So this would be the value of one unit of this particular item.

70
00:04:16,750 --> 00:04:22,600
And then we would just have to multiply it with the number of units of weight of this particular item

71
00:04:22,600 --> 00:04:24,190
that we have added to the knapsack.

72
00:04:24,190 --> 00:04:24,580
Okay.

73
00:04:24,580 --> 00:04:25,990
So that would be this.

74
00:04:25,990 --> 00:04:33,490
Again quickly explaining this like if we know that, for example, five units of mangoes okay, five

75
00:04:33,490 --> 00:04:37,450
units of weight, it can be kilograms or anything costs let's say $10.

76
00:04:37,450 --> 00:04:44,710
Now, if we were only able to add two units of weight to the knapsack, in that case the increment in

77
00:04:44,710 --> 00:04:50,050
the value would be this ten over here divided by five into two.

78
00:04:50,080 --> 00:04:50,500
Okay.

79
00:04:50,500 --> 00:04:52,120
And that's what we are doing over here.

80
00:04:52,120 --> 00:04:58,150
And once we are out of this for loop and we would come out of this for loop either when remaining weight

81
00:04:58,150 --> 00:05:03,970
becomes equal to zero, or if we have gone through all the given items, and then all that remains is

82
00:05:03,970 --> 00:05:05,230
to return the value.

83
00:05:05,980 --> 00:05:06,460
Okay.

84
00:05:06,460 --> 00:05:07,270
And that's it.

85
00:05:07,270 --> 00:05:13,270
Now let's go ahead and run this code and see if it's passing all the test cases okay.

86
00:05:13,270 --> 00:05:18,190
So there's an error I have named this wrongly decimal remaining weight.

87
00:05:18,190 --> 00:05:18,430
Right.

88
00:05:18,430 --> 00:05:20,380
So this w has to be caps.

89
00:05:20,380 --> 00:05:22,150
So let's correct that.

90
00:05:22,900 --> 00:05:25,990
Now let's go ahead and run this code and see if it's working.

91
00:05:26,890 --> 00:05:29,380
And you can see that it's passing all the test cases.

92
00:05:29,380 --> 00:05:33,010
So this is how we can solve the fractional knapsack problem.

93
00:05:33,010 --> 00:05:36,700
And notice that we have used a greedy algorithm to solve this question.