Question

A car hire company has one car at each of five depost a, b,c,d,e.a customer requires a car in each town namely A,B,C,D,E distances between deposits and town are given in the following distance matrix how should the cars be assigned so as to minimize the distance travelled
a. b. c. d. e
A. 160. 130. 175. 190. 200
B. 135 120. 130. 160 175
C. 140. 110. 155. 170. 185
D. 50. 50. 80. 80. 110
E. 55. 35. 70. 80. 105

Answer 1

Answer on Question #49265 – Math – Other

$A - e; \quad B - c; \quad C - b; \quad D - a; \quad E - d.$

Solution

Description of general idea of code below:

1. We have matrix $n \times n$.

2. Exhaustive search.

3. Every chosen element of row exclude whole corresponding column.

4. Thus, total number of different configurations $n!$.

5. For every configuration we calculate sum of the distances.

6. Among this sums we looking for minimal.

C#

```cpp

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace calculate_minimal_way

{

class Program

{

static void Main(string[] args)

{

string temp = "";

int[][] arr = new int[5][];

for (int i = 0; i < 5; i++)

{

temp = Console.ReadLine();

arr[i] = new int[5];

for(int j = 0; j < 5; j++)

{

arr[i][j] = Int32.Parse(temp.Split(' ')[j]);

}

}

int temp_sum = 0;

int min_sum = 9999999;

string pos_min = "";

for (int i = 0; i < 5; i++)

{

{ temp_sum = 0; List<int> B = new List<int>(5); List<int> C = new List<int>(5); List<int> D = new List<int>(5); List<int> E = new List<int>(5); B.AddRange(arr[1]); C.AddRange(arr[2]); D.AddRange(arr[3]); E.AddRange(arr[4]); B.RemoveAt(i); C.RemoveAt(i); D.RemoveAt(i); E.RemoveAt(i); for (int j = 0; j < 4; j++) { List<int> C_2 = new List<int>(4); List<int> D_2 = new List<int>(4); List<int> E_2 = new List<int>(4); C_2.AddRange(C); D_2.AddRange(D); E_2.AddRange(E); C_2.RemoveAt(j); D_2.RemoveAt(j); E_2.RemoveAt(j); for (int k = 0; k < 3; k++) { List<int> D_3 = new List<int>(3); List<int> E_3 = new List<int>(3); D_3.AddRange(D_2); E_3.AddRange(E_2); D_3.RemoveAt(k); E_3.RemoveAt(k); for (int h = 0; h < 2; h++) { List<int> E_4 = new List<int>(2); E_4.AddRange(E_3); E_4.RemoveAt(h); temp_sum = arr[0][i] + B[j] + C_2[k] + D_3[h] + E_4[0]; if (temp_sum < min_sum) { min_sum = temp_sum; pos_min = (i+1) + " " + (j+1) + " " + (k+1) + " " + (h+1) + " "; } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } } }

Result: min_sum 570.

Pos_min = 5 3 2 1, which means e, c, b, a respectively.

Thus, desirable distribution:

A - e

$$B - c$$ $$C - b$$ $$D - a$$ $$E - d$$

www.AssignmentExpert.com