1
00:00:00,110 --> 00:00:05,570
In the previous video, we have discussed the approach that we can take to solve this question.

2
00:00:05,570 --> 00:00:09,890
Let's now go ahead and write the pseudocode for the approach that we came up with.

3
00:00:09,890 --> 00:00:15,020
Now again, let's take the example where the capacity of the knapsack is 45.

4
00:00:15,020 --> 00:00:20,420
And this is the array which is given to us where each item is an array by itself.

5
00:00:20,420 --> 00:00:24,800
And the first item over here represents the profit that this item can give.

6
00:00:24,800 --> 00:00:29,180
If ten kilograms of this item were added to the knapsack.

7
00:00:29,180 --> 00:00:34,760
And we have seen that for solving this question, we would need to calculate the profit by weight ratio.

8
00:00:34,760 --> 00:00:38,030
So let's go ahead and calculate that and note it down over here.

9
00:00:38,030 --> 00:00:40,970
And to solve this question we would need a function.

10
00:00:40,970 --> 00:00:44,270
Let's just call it fract for fractional knapsack.

11
00:00:44,270 --> 00:00:48,320
And to this function we would pass the weight which is 45.

12
00:00:48,320 --> 00:00:51,350
In this case the array which is this array over here.

13
00:00:51,350 --> 00:00:57,590
And let's say we are also passing in to the function over here which indicates how many items are given

14
00:00:57,590 --> 00:00:58,040
to us.

15
00:00:58,040 --> 00:01:00,710
And in this case we are given five items.

16
00:01:00,710 --> 00:01:07,280
Now in the body of the function, the first thing that we would have to do is we would have to sort

17
00:01:07,310 --> 00:01:15,020
this array, which is given to us on the basis of the profit by weight ratio in reverse order, so that

18
00:01:15,020 --> 00:01:20,480
the first item in the array becomes the item with the highest profit by weight ratio.

19
00:01:20,480 --> 00:01:20,900
Okay.

20
00:01:20,900 --> 00:01:23,690
So let's go ahead and note that down over here.

21
00:01:23,690 --> 00:01:30,650
So we will sort the array which is given to us on the basis of the profit by weight ratio in reverse

22
00:01:30,650 --> 00:01:31,370
order.

23
00:01:31,370 --> 00:01:38,900
Now once we have done that we will set the remaining capacity that can be added to the knapsack to equal

24
00:01:38,900 --> 00:01:45,020
w, because at this point nothing has been added to the knapsack, and the profit or the value in the

25
00:01:45,020 --> 00:01:50,240
knapsack will be set to zero again, because for the same reason that nothing has been added to the

26
00:01:50,240 --> 00:01:51,500
knapsack so far.

27
00:01:51,590 --> 00:01:52,340
All right.

28
00:01:52,340 --> 00:01:58,640
And then we would have to write some code or do some operations over here to identify the maximum value

29
00:01:58,640 --> 00:02:00,500
that can be added to the knapsack.

30
00:02:00,500 --> 00:02:03,770
And ultimately we would just return the value.

31
00:02:03,770 --> 00:02:04,160
Okay.

32
00:02:04,160 --> 00:02:05,480
So this is the skeleton.

33
00:02:05,480 --> 00:02:09,620
Now let's go ahead and fill this part of the pseudocode.

34
00:02:09,620 --> 00:02:14,510
So what we would do is we would go through each item in the array.

35
00:02:14,510 --> 00:02:21,620
And remember at this point array has been sorted in the reverse order on the basis of the profit by

36
00:02:21,620 --> 00:02:22,310
weight ratio.

37
00:02:22,310 --> 00:02:27,050
So the first item that we get would have the highest profit by weight ratio.

38
00:02:27,080 --> 00:02:32,780
The second item in array at this point has the second highest profit by weight ratio.

39
00:02:32,780 --> 00:02:34,400
And it goes on in this manner.

40
00:02:34,400 --> 00:02:38,870
So at this point we would just iterate over each item in the array.

41
00:02:38,870 --> 00:02:43,910
And then we will check whether the remaining capacity is not zero.

42
00:02:43,910 --> 00:02:49,820
Because if it's zero, then nothing more can be added to the knapsack and we can just break out of the

43
00:02:49,820 --> 00:02:50,270
for loop.

44
00:02:50,270 --> 00:02:50,660
Okay.

45
00:02:50,660 --> 00:02:56,720
So if the remaining capacity is equal to zero, we'll just break out of the for loop or we'll just get

46
00:02:56,720 --> 00:02:57,350
out of it.

47
00:02:57,350 --> 00:03:05,420
But if it is not equal to zero, then we will have to decide how much of the particular item at hand

48
00:03:05,420 --> 00:03:08,270
can be included into the knapsack.

49
00:03:08,270 --> 00:03:11,750
Now again, there are two things to keep in mind with this regard.

50
00:03:11,750 --> 00:03:17,390
The first thing is how much is the remaining capacity that can be added to the knapsack?

51
00:03:17,390 --> 00:03:22,520
And the second is how much of the item at hand is given to us, like over here.

52
00:03:22,520 --> 00:03:29,000
For example, for this item, we just can add ten kilograms of that item to the knapsack because that's

53
00:03:29,000 --> 00:03:29,960
all that we have.

54
00:03:29,960 --> 00:03:34,700
Even if the remaining capacity is 40, we cannot add 40kg of this item.

55
00:03:34,700 --> 00:03:36,110
We can just add ten.

56
00:03:36,110 --> 00:03:43,670
So to identify the capacity of the item at hand that can be added to the knapsack, we have to identify

57
00:03:43,670 --> 00:03:50,090
the minimum between the remaining capacity that can be added to the knapsack and the item weight which

58
00:03:50,090 --> 00:03:51,950
is given to us in the array.

59
00:03:51,980 --> 00:03:58,730
Okay, so the minimum between these two would be the capacity that we can take of this particular item

60
00:03:58,730 --> 00:04:00,680
and add to the knapsack.

61
00:04:00,680 --> 00:04:01,160
Okay.

62
00:04:01,160 --> 00:04:05,690
And when we do that the value in the knapsack would increase okay.

63
00:04:05,690 --> 00:04:07,820
But by how much would it increase.

64
00:04:07,820 --> 00:04:14,930
The amount by which the value would increase is the product of the capacity that we did add.

65
00:04:15,450 --> 00:04:18,060
Multiplied with the per unit value.

66
00:04:18,060 --> 00:04:20,190
Okay, again, this is pretty straightforward.

67
00:04:20,190 --> 00:04:28,080
If one unit of something costs, let's say $10, then five units of that item would cost five into $10.

68
00:04:28,080 --> 00:04:28,440
Right.

69
00:04:28,440 --> 00:04:34,110
So in a similar manner, we would just need to multiply the capacity that we have decided to include

70
00:04:34,110 --> 00:04:39,330
into the knapsack for that particular item with the per unit value of that item.

71
00:04:39,330 --> 00:04:44,670
For example, if we take this item over here, we know that the per unit value is seven.

72
00:04:44,670 --> 00:04:48,300
And hypothetically let's say we're just taking five units.

73
00:04:48,300 --> 00:04:55,260
If that were the case, then the value that would be increased in the knapsack or the profit that would

74
00:04:55,260 --> 00:04:58,530
be increased in the knapsack would be seven into five.

75
00:04:58,530 --> 00:04:59,970
And that's what we're doing over here.

76
00:04:59,970 --> 00:05:00,330
Okay.

77
00:05:00,330 --> 00:05:07,410
So we are incrementing the value by the capacity multiplied with the per unit value of that particular

78
00:05:07,410 --> 00:05:08,070
item.

79
00:05:08,070 --> 00:05:13,620
And when this item has been added to the knapsack, there's one more thing that we have to do, which

80
00:05:13,620 --> 00:05:19,830
is to reduce the remaining capacity that can be added to the knapsack by the capacity that has been

81
00:05:19,830 --> 00:05:20,250
added.

82
00:05:20,250 --> 00:05:26,460
So the remaining capacity would equal the remaining capacity minus the capacity that we have added to

83
00:05:26,460 --> 00:05:27,030
the knapsack.

84
00:05:27,030 --> 00:05:27,870
And that's it.

85
00:05:27,870 --> 00:05:35,280
So in this way, once we get out of the for loop, we would have added the items to the knapsack in

86
00:05:35,280 --> 00:05:38,580
a manner that would maximize the value in the knapsack.

87
00:05:38,580 --> 00:05:41,400
And then we would just need to return the value.

88
00:05:41,400 --> 00:05:45,840
So this is the pseudocode for the approach that we've discussed in the previous video.

89
00:05:45,840 --> 00:05:51,750
Now in the next video let's go ahead and take a look at the complexity analysis for this approach.