Welcome back.
Let's now discuss how we can solve this question.
And for this, let's say that this is the array which is given to us.
Now when you take a look at the question, we can notice that this is an optimization problem.
We are asked to minimize the cost for flying half of the people to city A and the other half to city
B, so this is the constraint okay.
And we have to meet this constraint.
And we are asked an optimization problem because we have to do it in a manner that the cost involved
is the minimum okay.
So again clearly this is an optimization problem.
Now because this is an optimization problem.
Naturally we'll have the question in our mind whether we can solve this question using dynamic programming
and whether we can solve this question using greedy algorithms, because we know that dynamic programming
and greedy algorithms are used for optimization problems.
Okay.
So let's think about this.
First let's consider whether we can use dynamic programming.
Now over here we have these four elements in the example over here.
And for each person okay.
And every element represents a person.
And these are costs for flying this particular person to city A.
And this is the cost for flying this person to city B okay.
Now for each person we have two choices.
We can either fly this person to city A or we can fly this person to city B okay, so there are two
choices for each person.
Now let me just number the people over here.
So we have one, two, three and four.
And for person one.
We have seen that there are two choices now for each of these two branches.
Okay.
So again, this is the case where person one is flown to city A, and this is the branch where person
one is flown to city B.
Now for each of these branches, when we come to person number two again we have two choices.
We can fly person two to city A and we can fly person two to city B, and it goes on in this manner.
And again the tree over here will unfold in a manner that it keeps the constraint, which is that half
of the people have to be flown to city A and half of the people have to be flown to city B, so you
can see that there are choices involved.
And the recursive tree has branches.
And this over here indicates a high probability for overlapping subproblems.
So we have seen that previously that when you have a structure like this there is a high probability
for overlapping subproblems.
Now given all of these yes we can solve this question using dynamic programming now because over here
we are discussing greedy algorithms will not be discussing the detailed dynamic programming approach
as part of this video, but I have provided a detailed article on how you can solve this question using
various dynamic programming approaches.
All right.
So we have answered this question, and we have seen that we can solve this question using dynamic programming.
Now what about the greedy algorithm.
Can we solve this question using a greedy approach.
Let's think about that now.
In this question every person has to be flown either to city A or to city B, and the aim is that we
want to minimize the cost and fulfill the constraint, which is that half of the people have to be flown
to city A, and the other half have to be flown to city B.
Okay, now when you make choices for every person, which is whether to fly, that person to city A
or city B, the way that you have to choose it is in a way that it has the least cost impact to the
overall cost.
Okay, now let's see how this pans out.
Now for example, you have this person over here and you have two possibilities.
You can fly this person to city A, or you can fly this person to city B okay.
Now again you cannot minimize the cost to zero because ultimately this person has to be flown to city
A or city B.
Now when you take the difference of the costs involved, you can see that 20 -700 gives you -680.
Okay.
Now in a similar manner, if we take the difference of costs involved for these three people as well,
the differences are 400 -50 which is three 5900, -600 which is 302 hundred, -150 which is 50.
Okay.
Now if we were to sort the cost array based on the difference of costs involved, okay.
If you were to do that, notice that this is how the cost array would look like.
We'll have 20 comma 700.
Then we'll have 200 comma 150 because the difference over here is just 50.
And then we'll have 900 comma 600.
And finally we'll have 400 comma 50.
Okay.
Now once you have sorted the array in this manner, notice that the choices where we are just trying
to minimize the cost impact to the overall cost would be just choosing the first two people for city
A and the last two people for city B.
Okay, so this would be the optimal solution.
And again, the interesting thing to note over here is that these four choices are greedy choices,
or they are just locally optimal solutions or choices, which ultimately helps us to arrive at the global
optimum.
So what we are seeing over here is that the choice to send the first person to city A is the first locally
optimum solution or choice that we are making, okay, because it has the least impact to the overall
cost.
Even if this element over here was something like 100 comma 60, where the cost to fly to city A is
greater than the cost to fly to city B even then, because the difference between these two is 40.
And this is the least difference among these three and this one.
So even if this is the case, still we would choose city A for this particular person.
Because if we rather send this person to city B, we'd have to send another person to city A, and the
cost impact of that scenario would be greater.
Okay.
So again, what we're doing is at every step we're just making greedy choices or locally optimum choices
or solutions to arrive at the global solution.
Okay.
So this would be our second choice.
And this is our third choice.
And this is our.
Fourth choice, and by making just greedy choices, we are able to arrive at the global optimum solution.
Now let's take one more example to understand this thoroughly and to understand why this is in fact
the locally optimal solution, or the choice that has the least impact on the overall cost.
So let's try to understand that.
And for that, let's take this example over here where we just have two people.
So this is the first person and this is the second person.
And these are the respective costs okay.
Now for this element the difference between costs is 900 -600 which is 300.
And for person number two the difference is 200 -150 which is equal to 50.
Now if we go ahead and sort these elements based on these differences, this is how the costs array
would look like.
So we have 200 comma 150 over here and 900 comma 600 over here.
And based on the approach that we have discussed, we would choose CTA for the first person and city
B for the second person.
Now notice over here that for both the people, city A is costlier like you have 200 which is greater
than 150.
And over here you have 900 which is greater than 600.
But we have chosen to send this particular person to CTA.
Now, again, let me just name this person as Mr. X and let's say this is miss Y.
Okay.
So we have x and y.
And because we just have two people, it's pretty easy to visualize the two possibilities.
I could send this person to a and this person to city B, or I could send this person to city B and
this person to city A okay.
Now we have seen that as per the solution that we have discussed, we will choose to send this person
to city A.
But if, on the contrary, we had chosen to send this person to city B, then we would have to send
this person to city A and the overall cost in this scenario would be higher than the overall cost in
this scenario.
Now notice in this scenario, the overall cost is 200 plus 600, which is 800.
But in this scenario the overall cost would be 150 plus 900 which is 1050.
Okay.
So that's why sending person X to city A has the minimum impact on the overall cost.
And that's because there is a constraint that half of the people have to be sent to city A, and the
other half have to be sent to city B.
Okay.
Now let's take one more example to summarize the greedy approach that we have discussed over here.
So let's say these are the four people.
Now we have discussed that what we will do is we'll go ahead and find the difference between the costs
for each person.
Now, once we have that, we'll just go ahead and sort the costs array on the basis of this difference.
So the cost array at this point would look like this okay.
And we are guaranteed in the question that the number of elements in the cost array will be an even
number.
So after we have sorted the cost array, all that we need to do is we need to identify the middle point.
And the first half of people would be sent to city A, and the other half of people would be sent to
city B.
Now when we do that, the costs involved are 2200, 650.
And this would give us the minimum cost.
And the reason for this is that when we choose to send these people to city A, it has the lowest cost
impact on the overall cost in a way that meets the constraints of the question.
So this is the approach we can use to solve this question.
And notice that this is a greedy algorithm, because at every point we are just choosing the choice
that has the least impact on the overall cost, which is in fact a greedy choice.