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

2
00:00:01,160 --> 00:00:05,240
Let's now think about the approach that we can take to solve this question.

3
00:00:05,240 --> 00:00:10,670
And for discussing that, let's take this example where this is the array which is given to us.

4
00:00:10,670 --> 00:00:14,450
And the capacity of the knapsack is 45.

5
00:00:14,450 --> 00:00:14,900
Okay.

6
00:00:14,900 --> 00:00:21,740
So again remember the question mentions that each item in the array is an array by itself which has

7
00:00:21,740 --> 00:00:22,460
two elements.

8
00:00:22,460 --> 00:00:29,150
And the first element over here represents the profit of that particular item, and the second element

9
00:00:29,150 --> 00:00:31,670
represents the weight of that particular item.

10
00:00:31,670 --> 00:00:33,350
And you can take any units.

11
00:00:33,350 --> 00:00:39,590
Now if you were to take kilogram, this would imply ten kilograms of this particular item, if added

12
00:00:39,590 --> 00:00:44,900
to the knapsack, would increase the profit in the knapsack by 70 units.

13
00:00:44,900 --> 00:00:52,340
And if we take this as kilograms, then this also would be kilograms, and it would imply that the maximum

14
00:00:52,340 --> 00:00:56,480
weight that can be added to the knapsack is 45kg.

15
00:00:56,480 --> 00:01:03,560
So we have understood the question now also do remember in the question it's mentioned that we can take

16
00:01:03,560 --> 00:01:05,240
fractions of an item.

17
00:01:05,240 --> 00:01:05,600
Okay.

18
00:01:05,600 --> 00:01:10,370
Now what would be some of the approaches that can be taken to solve this question.

19
00:01:10,370 --> 00:01:17,360
Maybe person A would say, let's first add this particular item to the knapsack, because it has the

20
00:01:17,360 --> 00:01:20,270
highest value among all the items over here.

21
00:01:20,270 --> 00:01:25,010
So you have 70 over here, 90 over here, 150 over here, 80 and 100 over here.

22
00:01:25,010 --> 00:01:26,900
So this is the highest profit.

23
00:01:26,900 --> 00:01:33,230
And therefore maybe person A tells that let's add this particular item first to the knapsack.

24
00:01:33,230 --> 00:01:40,670
Now another person, let's say person B may say let's add this particular item to the knapsack because

25
00:01:40,670 --> 00:01:42,230
it has the least weight.

26
00:01:42,230 --> 00:01:48,230
And if I add the item with the least weight into the knapsack first, then probably I can keep adding

27
00:01:48,230 --> 00:01:53,030
more items to the knapsack and in that manner maximize my profit.

28
00:01:53,030 --> 00:01:56,480
So probably this is what person B would advocate.

29
00:01:56,480 --> 00:01:56,960
Okay.

30
00:01:56,960 --> 00:02:00,710
And again notice this has the lowest weight among all of these other weights.

31
00:02:00,710 --> 00:02:05,450
So ten is the lowest value among 1020 3015 and 20.

32
00:02:05,450 --> 00:02:12,110
Now what do you think is any of these two approaches the right approach that we should take.

33
00:02:12,110 --> 00:02:12,980
What do you think?

34
00:02:12,980 --> 00:02:20,930
Now, the truth, for that matter is it's not only profit or weight that determines which item gives

35
00:02:20,930 --> 00:02:27,800
us the maximum benefit when we add that particular item to the knapsack, but rather it's the profit

36
00:02:27,800 --> 00:02:29,450
by weight ratio.

37
00:02:29,450 --> 00:02:29,870
Okay.

38
00:02:29,870 --> 00:02:33,290
Because again, you have a knapsack with a fixed capacity.

39
00:02:33,290 --> 00:02:41,150
And therefore what we want is for every unit of capacity or weight that gets increased in the knapsack

40
00:02:41,150 --> 00:02:45,440
by adding something to the knapsack, we want the maximum profit.

41
00:02:45,440 --> 00:02:45,800
Okay.

42
00:02:45,800 --> 00:02:50,210
So for per unit weight we want the highest profit.

43
00:02:50,210 --> 00:02:57,230
And to identify the item that would enable this, we would have to take the profit by weight ratio.

44
00:02:57,230 --> 00:03:03,590
And then whichever item among the items over here has the highest profit by weight ratio, that would

45
00:03:03,590 --> 00:03:07,460
be the item that we would have to first add to the knapsack.

46
00:03:07,460 --> 00:03:11,540
And if possible, we would just fill the knapsack with that particular item.

47
00:03:11,540 --> 00:03:11,930
Okay.

48
00:03:11,930 --> 00:03:14,330
So let's go ahead and see how that works out.

49
00:03:14,330 --> 00:03:16,730
And for that let me make some space over here.

50
00:03:16,730 --> 00:03:21,440
So again, what we have so far discussed is that we are going to make choices.

51
00:03:21,440 --> 00:03:27,590
And again, the solution or filling the knapsack is going to be a step by step process.

52
00:03:27,590 --> 00:03:31,340
And at every step we are going to make a greedy choice.

53
00:03:31,340 --> 00:03:37,280
Or we are going to pick the item that has the highest profit by weight ratio.

54
00:03:37,280 --> 00:03:44,810
So notice how the problem can be solved using a greedy algorithm, because it is satisfying the greedy

55
00:03:44,810 --> 00:03:50,150
choice property and it's satisfying the optimal substructure property.

56
00:03:50,150 --> 00:03:56,600
Now, when I say that this problem satisfies the greedy choice property, what do I mean with it?

57
00:03:56,600 --> 00:04:05,960
Notice at every point we are making the locally optimal choice by trying to pick the item with the highest

58
00:04:05,960 --> 00:04:09,770
profit by weight ratio and with locally optimal choice.

59
00:04:09,770 --> 00:04:10,670
What do I mean?

60
00:04:10,670 --> 00:04:13,460
We are not trying to optimize anything globally.

61
00:04:13,460 --> 00:04:15,920
I'm just trying to make one choice.

62
00:04:16,190 --> 00:04:23,930
And in that one choice at every step, I'm just choosing the item that has the highest profit by weight

63
00:04:23,930 --> 00:04:24,440
ratio.

64
00:04:24,440 --> 00:04:31,190
So it's the locally optimal choice that I am making, or I'm making the optimal choice at this particular

65
00:04:31,190 --> 00:04:35,210
instance, which gives me the highest value or impact.

66
00:04:35,210 --> 00:04:35,660
Okay.

67
00:04:35,660 --> 00:04:39,980
So again that's the item with the highest profit by weight ratio.

68
00:04:39,980 --> 00:04:44,810
And that's why this question satisfies the greedy choice property.

69
00:04:44,810 --> 00:04:51,350
Because if we keep doing that, we would finally end up using all the capacity of the knapsack.

70
00:04:51,350 --> 00:04:56,000
And we would have filled the maximum possible value into the knapsack.

71
00:04:56,000 --> 00:04:59,540
And that's the global optimal solution which we are trying to achieve.

72
00:04:59,780 --> 00:05:03,200
By making these locally optimal choices.

73
00:05:03,200 --> 00:05:07,370
So this question over here satisfies the greedy choice property.

74
00:05:07,370 --> 00:05:12,590
And it also satisfies the optimal substructure property.

75
00:05:12,590 --> 00:05:19,670
Because the optimal solution to the problem contains the optimal solution to subproblems.

76
00:05:19,670 --> 00:05:24,260
And over here, the subproblems are the various steps that we have to take.

77
00:05:24,260 --> 00:05:24,590
Right?

78
00:05:24,590 --> 00:05:29,510
So when we have to make a choice for the first time, we are actually solving a subproblem.

79
00:05:29,510 --> 00:05:36,110
And when you compare the optimal solution to the problem at hand, which is when we would have filled

80
00:05:36,110 --> 00:05:42,320
the knapsack with the correct items in their correct proportions, such that the profit is maximized

81
00:05:42,320 --> 00:05:44,240
and the constraint is met.

82
00:05:44,240 --> 00:05:51,350
So when we take a look at the globally optimal solution, and when we think of each subproblem where

83
00:05:51,350 --> 00:05:56,960
we have some items may be in the knapsack, and we are tasked to make a choice and add something more

84
00:05:56,960 --> 00:05:57,920
to the knapsack.

85
00:05:57,920 --> 00:06:03,260
So when you take a look at the solution to that particular subproblem, you will find that the solution

86
00:06:03,260 --> 00:06:07,490
to those subproblems are there in the global solution as well.

87
00:06:07,490 --> 00:06:12,230
And therefore this question follows the optimal substructure property as well.

88
00:06:12,230 --> 00:06:18,710
Now, to thoroughly understand what we have discussed so far, let's just quickly dry run how the algorithm

89
00:06:18,710 --> 00:06:20,060
would solve this question.

90
00:06:20,060 --> 00:06:24,200
So we are given a knapsack which has a capacity of 45kg.

91
00:06:24,200 --> 00:06:26,930
And then we are given this array of items.

92
00:06:26,930 --> 00:06:33,200
Now let's go ahead and identify the profit by weight ratio of each of these items.

93
00:06:33,200 --> 00:06:39,320
For the first item the ratio would be 70 divided by ten which is equal to seven.

94
00:06:40,230 --> 00:06:47,160
For the second item, the profit by weight ratio is 90 by 20, which is equal to 4.5.

95
00:06:47,190 --> 00:06:54,090
Similarly, the ratio for the next item is 150 by 30, which is equal to five, and the ratio for the

96
00:06:54,090 --> 00:07:01,770
next item is 80 divided by 15, which is five one by three, and the final ratio is 100 by 20, which

97
00:07:01,770 --> 00:07:03,450
is also equal to five.

98
00:07:03,480 --> 00:07:08,010
Now it's given that the capacity of the knapsack is 45 units.

99
00:07:08,010 --> 00:07:13,140
So the highest profit by weight ratio is for this item over here.

100
00:07:13,140 --> 00:07:20,040
And the maximum amount of this item that we can take is ten kilograms because that's all that we have

101
00:07:20,040 --> 00:07:20,430
okay.

102
00:07:20,430 --> 00:07:26,550
So because this has the highest profit by weight ratio and because ten is less than equal to 45.

103
00:07:26,550 --> 00:07:32,700
So let's go ahead and include ten kilograms of this item into our knapsack.

104
00:07:32,700 --> 00:07:40,530
So when we do that the capacity of the knapsack would reduce to 45 minus ten, which is equal to 35.

105
00:07:40,530 --> 00:07:49,290
So we can add items that way a total of 35kg into the knapsack after having added ten kilograms of item

106
00:07:49,290 --> 00:07:49,770
one.

107
00:07:49,770 --> 00:07:51,000
So we proceed.

108
00:07:51,000 --> 00:07:57,090
And when we take a look at the profit by weight ratio of the remaining items, we can see that this

109
00:07:57,090 --> 00:08:04,080
is the second highest value, or among these, this has the highest value, and the maximum amount of

110
00:08:04,080 --> 00:08:09,000
this particular item that is made available to us is 15kg.

111
00:08:09,000 --> 00:08:18,240
And because 15 is less than or equal to 35, we decide to add 15kg of this particular item to the knapsack.

112
00:08:18,240 --> 00:08:26,280
Now the remaining capacity of the knapsack changes to 35 -15, which is equal to 20.

113
00:08:26,280 --> 00:08:30,060
So again we proceed among these three items.

114
00:08:30,300 --> 00:08:37,320
The items with the highest profit by weight ratio are this item over here and this item over here.

115
00:08:37,320 --> 00:08:42,510
And because they have the same profit by weight ratio, we can take any of these.

116
00:08:42,510 --> 00:08:46,650
Now let's say we are proceeding with this one over here okay.

117
00:08:46,650 --> 00:08:55,710
And because we have 30kg of this item available but the remaining capacity is only 20, we can only

118
00:08:55,710 --> 00:08:59,580
take 20 units or 20kg of this item.

119
00:08:59,580 --> 00:09:01,740
And we add that to our knapsack.

120
00:09:01,740 --> 00:09:08,670
And when we do that, the remaining capacity that can be added to the knapsack becomes 20 -20, which

121
00:09:08,670 --> 00:09:14,940
is equal to zero, which means that at this point our knapsack is completely filled.

122
00:09:14,940 --> 00:09:21,330
Now let's go ahead and compute the value or the profit of items in the knapsack, so that we can return

123
00:09:21,330 --> 00:09:21,690
that.

124
00:09:21,690 --> 00:09:25,440
So we have ten kilograms of this particular item.

125
00:09:25,440 --> 00:09:30,690
And therefore the profit of this item that is there in the knapsack is 70.

126
00:09:30,720 --> 00:09:31,110
Okay.

127
00:09:31,110 --> 00:09:34,290
Because the complete item is there in the knapsack.

128
00:09:34,290 --> 00:09:40,200
And when it comes to this item over here, we have 20kg in the knapsack.

129
00:09:40,200 --> 00:09:44,400
Now if we had 30kg the profit would be 150.

130
00:09:44,430 --> 00:09:53,370
Therefore, the profit of 20kg is equal to 150 into 20 divided by 30 okay.

131
00:09:53,370 --> 00:09:59,220
And this simplifies to five into 20 which is equal to 100.

132
00:09:59,220 --> 00:10:07,020
So the profit in the knapsack on account of the presence of this particular item is equal to five into

133
00:10:07,020 --> 00:10:08,760
20, which is 100.

134
00:10:08,760 --> 00:10:15,060
Now what about this item over here we have 15kg of this item in the knapsack.

135
00:10:15,060 --> 00:10:18,960
And that's the complete amount of this item that we have.

136
00:10:18,960 --> 00:10:24,810
And therefore the profit in the knapsack on account of this item is equal to 80.

137
00:10:24,900 --> 00:10:26,280
So that's 80.

138
00:10:26,310 --> 00:10:31,020
Or you can think of it as five one by three into 15 as well.

139
00:10:31,020 --> 00:10:35,580
And again I'm just showing a calculation over here so that you understand one more way in which you

140
00:10:35,580 --> 00:10:36,510
could write the code.

141
00:10:36,510 --> 00:10:41,130
Now five one by three is the unit profit for this item.

142
00:10:41,130 --> 00:10:44,940
And 15 is the units or the weight that is being added.

143
00:10:44,940 --> 00:10:51,270
So if we multiply five one by three into 15, we will get the profit incremented in the knapsack because

144
00:10:51,270 --> 00:10:53,100
of the presence of this particular item.

145
00:10:53,100 --> 00:10:57,450
Now in this case five one by three into 15 will again give you 80.

146
00:10:57,450 --> 00:11:05,490
So the total profit in the knapsack at this point is 70 plus 100 plus 80, which is equal to 250.

147
00:11:05,490 --> 00:11:08,070
And that would be the answer that we will return.

148
00:11:08,070 --> 00:11:10,920
So this is how we can solve this question.

149
00:11:10,920 --> 00:11:16,830
And notice that we have used a greedy algorithm to solve this, where at every step we are just trying

150
00:11:16,830 --> 00:11:20,580
to pick the item with the highest profit by weight ratio.

151
00:11:20,580 --> 00:11:26,790
And in this way we are able to maximize the profit that we can include in the knapsack.