%% Assign Taxis to Maximize Profit
% Assign taxis to routes such that the profit is maximized.
% A taxi company has several ride requests from across the city. The company wants to dispatch its limited number of taxis in a way that makes the most money.
% This table shows the estimated taxi fare for each of five ride requests. Only three of the five ride requests can be filled.
% $$\begin{array}{|c|l|l|l|}
% \hline & \mbox{Ride 1} & \mbox{Ride 2} & \mbox{Ride 3} & \mbox{Ride 4} & \mbox{Ride 5}\\
% \hline \mbox{Cab A} & \$5.70 & \$6.30& \$3.10 & \$4.80 & \$3.50\\
% \hline \mbox{Cab B} & \$5.80 & \$6.40& \$3.30 & \$4.70 & \$3.20\\
% \hline \mbox{Cab C} & \$5.70 & \$6.30 & \$3.20 & \$4.90 & \$3.40\\ \hline \end{array}$$
%
% Create a profits matrix to represent the profits of each taxi ride.

P = [5.7 6.3 3.1 4.8 3.5
     5.8 6.4 3.3 4.7 3.2
     5.7 6.3 3.2 4.9 3.4];

%
% Use matchpairs to match the taxis to the most profitable rides. Specify three outputs to return any unmatched rows and columns, and the 'max' option to maximize the profits. Specify the cost of unassignment as zero, since the company makes no money from unfilled taxis or ride requests.

costUnmatched = 0;
[M,uR,uC] = matchpairs(P,costUnmatched,'max')

%
% matchpairs calculates the most profitable rides to fill. The solution leaves ride requests 3 and 5 unfilled.
% $$\begin{array}{|c|l|l|l|}
% \hline & \mbox{Ride 1} & \mbox{Ride 2} & \mbox{Ride 3} & \mbox{Ride 4} & \mbox{Ride 5}\\
% \hline \mbox{Cab A} & \mathbf{\$5.70} & \$6.30& \$3.10 & \$4.80 & \$3.50\\
% \hline \mbox{Cab B} & \$5.80 & \mathbf{\$6.40} & \$3.30 & \$4.70 & \$3.20\\
% \hline \mbox{Cab C} & \$5.70 & \$6.30 & \$3.20 & \mathbf{\$4.90} & \$3.40\\ \hline \end{array}$$
%
% Calculate the total profits for the calculated solution. Since costUnmatched is zero, you only need to add together the profits from each match.

TotalProfits = sum(P(sub2ind(size(P), M(:,1), M(:,2))))

%
% Copyright 2018 The MathWorks, Inc.