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

2
00:00:01,190 --> 00:00:04,340
Let's now discuss how we can solve this question.

3
00:00:04,340 --> 00:00:08,270
And for this, let's say that this is the array which is given to us.

4
00:00:08,270 --> 00:00:13,910
Now when you take a look at the question, we can notice that this is an optimization problem.

5
00:00:13,910 --> 00:00:21,200
We are asked to minimize the cost for flying half of the people to city A and the other half to city

6
00:00:21,200 --> 00:00:23,450
B, so this is the constraint okay.

7
00:00:23,450 --> 00:00:26,450
And we have to meet this constraint.

8
00:00:26,450 --> 00:00:32,480
And we are asked an optimization problem because we have to do it in a manner that the cost involved

9
00:00:32,480 --> 00:00:34,100
is the minimum okay.

10
00:00:34,100 --> 00:00:37,130
So again clearly this is an optimization problem.

11
00:00:37,130 --> 00:00:39,980
Now because this is an optimization problem.

12
00:00:39,980 --> 00:00:45,800
Naturally we'll have the question in our mind whether we can solve this question using dynamic programming

13
00:00:45,800 --> 00:00:53,000
and whether we can solve this question using greedy algorithms, because we know that dynamic programming

14
00:00:53,000 --> 00:00:58,040
and greedy algorithms are used for optimization problems.

15
00:00:58,040 --> 00:00:58,520
Okay.

16
00:00:58,520 --> 00:01:00,380
So let's think about this.

17
00:01:00,380 --> 00:01:05,150
First let's consider whether we can use dynamic programming.

18
00:01:05,150 --> 00:01:10,190
Now over here we have these four elements in the example over here.

19
00:01:10,190 --> 00:01:12,350
And for each person okay.

20
00:01:12,350 --> 00:01:14,480
And every element represents a person.

21
00:01:14,480 --> 00:01:17,990
And these are costs for flying this particular person to city A.

22
00:01:17,990 --> 00:01:21,260
And this is the cost for flying this person to city B okay.

23
00:01:21,260 --> 00:01:24,710
Now for each person we have two choices.

24
00:01:24,710 --> 00:01:32,750
We can either fly this person to city A or we can fly this person to city B okay, so there are two

25
00:01:32,750 --> 00:01:34,850
choices for each person.

26
00:01:34,850 --> 00:01:37,550
Now let me just number the people over here.

27
00:01:37,550 --> 00:01:39,770
So we have one, two, three and four.

28
00:01:39,770 --> 00:01:42,230
And for person one.

29
00:01:42,840 --> 00:01:47,880
We have seen that there are two choices now for each of these two branches.

30
00:01:47,910 --> 00:01:48,330
Okay.

31
00:01:48,330 --> 00:01:54,720
So again, this is the case where person one is flown to city A, and this is the branch where person

32
00:01:54,720 --> 00:01:56,730
one is flown to city B.

33
00:01:56,790 --> 00:02:02,580
Now for each of these branches, when we come to person number two again we have two choices.

34
00:02:02,580 --> 00:02:09,030
We can fly person two to city A and we can fly person two to city B, and it goes on in this manner.

35
00:02:09,030 --> 00:02:16,470
And again the tree over here will unfold in a manner that it keeps the constraint, which is that half

36
00:02:16,470 --> 00:02:23,880
of the people have to be flown to city A and half of the people have to be flown to city B, so you

37
00:02:23,880 --> 00:02:26,370
can see that there are choices involved.

38
00:02:26,370 --> 00:02:29,610
And the recursive tree has branches.

39
00:02:29,610 --> 00:02:35,490
And this over here indicates a high probability for overlapping subproblems.

40
00:02:35,490 --> 00:02:40,830
So we have seen that previously that when you have a structure like this there is a high probability

41
00:02:40,830 --> 00:02:42,450
for overlapping subproblems.

42
00:02:42,450 --> 00:02:49,200
Now given all of these yes we can solve this question using dynamic programming now because over here

43
00:02:49,200 --> 00:02:54,930
we are discussing greedy algorithms will not be discussing the detailed dynamic programming approach

44
00:02:54,930 --> 00:03:01,860
as part of this video, but I have provided a detailed article on how you can solve this question using

45
00:03:01,860 --> 00:03:04,290
various dynamic programming approaches.

46
00:03:04,290 --> 00:03:04,950
All right.

47
00:03:04,950 --> 00:03:10,740
So we have answered this question, and we have seen that we can solve this question using dynamic programming.

48
00:03:10,740 --> 00:03:13,380
Now what about the greedy algorithm.

49
00:03:13,380 --> 00:03:16,560
Can we solve this question using a greedy approach.

50
00:03:16,560 --> 00:03:18,330
Let's think about that now.

51
00:03:18,330 --> 00:03:28,140
In this question every person has to be flown either to city A or to city B, and the aim is that we

52
00:03:28,140 --> 00:03:34,500
want to minimize the cost and fulfill the constraint, which is that half of the people have to be flown

53
00:03:34,500 --> 00:03:38,580
to city A, and the other half have to be flown to city B.

54
00:03:38,580 --> 00:03:44,700
Okay, now when you make choices for every person, which is whether to fly, that person to city A

55
00:03:44,700 --> 00:03:54,300
or city B, the way that you have to choose it is in a way that it has the least cost impact to the

56
00:03:54,300 --> 00:03:55,650
overall cost.

57
00:03:55,650 --> 00:03:58,140
Okay, now let's see how this pans out.

58
00:03:58,140 --> 00:04:02,550
Now for example, you have this person over here and you have two possibilities.

59
00:04:02,550 --> 00:04:07,620
You can fly this person to city A, or you can fly this person to city B okay.

60
00:04:07,620 --> 00:04:14,910
Now again you cannot minimize the cost to zero because ultimately this person has to be flown to city

61
00:04:14,910 --> 00:04:16,110
A or city B.

62
00:04:16,140 --> 00:04:24,300
Now when you take the difference of the costs involved, you can see that 20 -700 gives you -680.

63
00:04:24,330 --> 00:04:24,900
Okay.

64
00:04:24,900 --> 00:04:30,870
Now in a similar manner, if we take the difference of costs involved for these three people as well,

65
00:04:30,870 --> 00:04:39,900
the differences are 400 -50 which is three 5900, -600 which is 302 hundred, -150 which is 50.

66
00:04:39,900 --> 00:04:40,320
Okay.

67
00:04:40,320 --> 00:04:46,350
Now if we were to sort the cost array based on the difference of costs involved, okay.

68
00:04:46,350 --> 00:04:50,850
If you were to do that, notice that this is how the cost array would look like.

69
00:04:50,850 --> 00:04:52,680
We'll have 20 comma 700.

70
00:04:52,680 --> 00:04:57,750
Then we'll have 200 comma 150 because the difference over here is just 50.

71
00:04:57,750 --> 00:05:00,210
And then we'll have 900 comma 600.

72
00:05:00,210 --> 00:05:02,760
And finally we'll have 400 comma 50.

73
00:05:02,760 --> 00:05:03,210
Okay.

74
00:05:03,210 --> 00:05:09,960
Now once you have sorted the array in this manner, notice that the choices where we are just trying

75
00:05:09,960 --> 00:05:17,970
to minimize the cost impact to the overall cost would be just choosing the first two people for city

76
00:05:17,970 --> 00:05:21,300
A and the last two people for city B.

77
00:05:21,300 --> 00:05:23,910
Okay, so this would be the optimal solution.

78
00:05:23,910 --> 00:05:30,510
And again, the interesting thing to note over here is that these four choices are greedy choices,

79
00:05:30,510 --> 00:05:37,890
or they are just locally optimal solutions or choices, which ultimately helps us to arrive at the global

80
00:05:37,890 --> 00:05:38,550
optimum.

81
00:05:38,820 --> 00:05:47,190
So what we are seeing over here is that the choice to send the first person to city A is the first locally

82
00:05:47,190 --> 00:05:53,220
optimum solution or choice that we are making, okay, because it has the least impact to the overall

83
00:05:53,220 --> 00:05:53,850
cost.

84
00:05:53,850 --> 00:06:01,470
Even if this element over here was something like 100 comma 60, where the cost to fly to city A is

85
00:06:01,470 --> 00:06:07,890
greater than the cost to fly to city B even then, because the difference between these two is 40.

86
00:06:07,890 --> 00:06:11,790
And this is the least difference among these three and this one.

87
00:06:11,790 --> 00:06:17,760
So even if this is the case, still we would choose city A for this particular person.

88
00:06:17,760 --> 00:06:24,300
Because if we rather send this person to city B, we'd have to send another person to city A, and the

89
00:06:24,300 --> 00:06:27,270
cost impact of that scenario would be greater.

90
00:06:27,270 --> 00:06:27,690
Okay.

91
00:06:27,690 --> 00:06:34,380
So again, what we're doing is at every step we're just making greedy choices or locally optimum choices

92
00:06:34,380 --> 00:06:37,860
or solutions to arrive at the global solution.

93
00:06:37,860 --> 00:06:38,250
Okay.

94
00:06:38,250 --> 00:06:40,080
So this would be our second choice.

95
00:06:40,080 --> 00:06:41,700
And this is our third choice.

96
00:06:41,700 --> 00:06:42,450
And this is our.

97
00:06:42,670 --> 00:06:49,960
Fourth choice, and by making just greedy choices, we are able to arrive at the global optimum solution.

98
00:06:49,990 --> 00:06:57,310
Now let's take one more example to understand this thoroughly and to understand why this is in fact

99
00:06:57,310 --> 00:07:04,240
the locally optimal solution, or the choice that has the least impact on the overall cost.

100
00:07:04,240 --> 00:07:05,770
So let's try to understand that.

101
00:07:05,770 --> 00:07:09,940
And for that, let's take this example over here where we just have two people.

102
00:07:09,940 --> 00:07:13,270
So this is the first person and this is the second person.

103
00:07:13,270 --> 00:07:15,610
And these are the respective costs okay.

104
00:07:15,610 --> 00:07:21,490
Now for this element the difference between costs is 900 -600 which is 300.

105
00:07:21,490 --> 00:07:28,150
And for person number two the difference is 200 -150 which is equal to 50.

106
00:07:28,180 --> 00:07:34,840
Now if we go ahead and sort these elements based on these differences, this is how the costs array

107
00:07:34,840 --> 00:07:35,650
would look like.

108
00:07:35,650 --> 00:07:40,720
So we have 200 comma 150 over here and 900 comma 600 over here.

109
00:07:40,720 --> 00:07:47,080
And based on the approach that we have discussed, we would choose CTA for the first person and city

110
00:07:47,080 --> 00:07:49,000
B for the second person.

111
00:07:49,420 --> 00:07:57,190
Now notice over here that for both the people, city A is costlier like you have 200 which is greater

112
00:07:57,190 --> 00:07:58,090
than 150.

113
00:07:58,090 --> 00:08:01,390
And over here you have 900 which is greater than 600.

114
00:08:01,390 --> 00:08:05,470
But we have chosen to send this particular person to CTA.

115
00:08:05,500 --> 00:08:11,860
Now, again, let me just name this person as Mr. X and let's say this is miss Y.

116
00:08:11,860 --> 00:08:12,460
Okay.

117
00:08:13,060 --> 00:08:15,280
So we have x and y.

118
00:08:15,280 --> 00:08:20,590
And because we just have two people, it's pretty easy to visualize the two possibilities.

119
00:08:20,590 --> 00:08:27,520
I could send this person to a and this person to city B, or I could send this person to city B and

120
00:08:27,520 --> 00:08:29,380
this person to city A okay.

121
00:08:29,380 --> 00:08:33,880
Now we have seen that as per the solution that we have discussed, we will choose to send this person

122
00:08:33,880 --> 00:08:34,630
to city A.

123
00:08:34,630 --> 00:08:41,170
But if, on the contrary, we had chosen to send this person to city B, then we would have to send

124
00:08:41,170 --> 00:08:48,040
this person to city A and the overall cost in this scenario would be higher than the overall cost in

125
00:08:48,040 --> 00:08:48,760
this scenario.

126
00:08:48,760 --> 00:08:54,670
Now notice in this scenario, the overall cost is 200 plus 600, which is 800.

127
00:08:54,670 --> 00:09:01,120
But in this scenario the overall cost would be 150 plus 900 which is 1050.

128
00:09:01,120 --> 00:09:01,510
Okay.

129
00:09:01,510 --> 00:09:09,070
So that's why sending person X to city A has the minimum impact on the overall cost.

130
00:09:09,070 --> 00:09:15,160
And that's because there is a constraint that half of the people have to be sent to city A, and the

131
00:09:15,160 --> 00:09:18,130
other half have to be sent to city B.

132
00:09:18,220 --> 00:09:18,670
Okay.

133
00:09:18,670 --> 00:09:23,710
Now let's take one more example to summarize the greedy approach that we have discussed over here.

134
00:09:23,710 --> 00:09:26,170
So let's say these are the four people.

135
00:09:26,170 --> 00:09:31,540
Now we have discussed that what we will do is we'll go ahead and find the difference between the costs

136
00:09:31,540 --> 00:09:32,800
for each person.

137
00:09:32,800 --> 00:09:39,970
Now, once we have that, we'll just go ahead and sort the costs array on the basis of this difference.

138
00:09:39,970 --> 00:09:43,450
So the cost array at this point would look like this okay.

139
00:09:43,450 --> 00:09:49,090
And we are guaranteed in the question that the number of elements in the cost array will be an even

140
00:09:49,090 --> 00:09:49,630
number.

141
00:09:49,630 --> 00:09:55,870
So after we have sorted the cost array, all that we need to do is we need to identify the middle point.

142
00:09:55,870 --> 00:10:03,550
And the first half of people would be sent to city A, and the other half of people would be sent to

143
00:10:03,550 --> 00:10:04,240
city B.

144
00:10:04,270 --> 00:10:09,490
Now when we do that, the costs involved are 2200, 650.

145
00:10:09,490 --> 00:10:12,130
And this would give us the minimum cost.

146
00:10:12,130 --> 00:10:19,690
And the reason for this is that when we choose to send these people to city A, it has the lowest cost

147
00:10:19,690 --> 00:10:25,690
impact on the overall cost in a way that meets the constraints of the question.

148
00:10:25,690 --> 00:10:29,620
So this is the approach we can use to solve this question.

149
00:10:29,620 --> 00:10:35,290
And notice that this is a greedy algorithm, because at every point we are just choosing the choice

150
00:10:35,290 --> 00:10:40,780
that has the least impact on the overall cost, which is in fact a greedy choice.