Franky Colombo is undergoing preparations to set sail for Wakanda. He has secured the appropriate funding and has purchased several ships. He now needs to recruit 100 sailors to join him on his journey. He has decided to recruit these sailors from different port cities along the coast of Africa. There are W such cities and in each city, there are n_i sailors, i=1,2....,W. Assume that . Hence, there are enough sailors in Spain to meet Franky's demand. All the sailors in Africa are currently employed and earn an annual salary. The salary of sailor j in the city i is c_ij, i=1,2,.....,T; j=1,2,....n_i. Sailors will agree to join Franky's fleet even if they are offered a salary that is lower than their current pay.

However, since sailors are known to compare salaries, Franky will need to pay all 100 sailors the same salary in order to keep them happy and avoid a mutiny at sea. At each city where sailors are recruited, Franky will calculate the average salary of the sailors joining his fleet (from that given city). At the end of the recruitment process, the highest average salary among the T cities will be the salary paid to all 100 sailors.

E.g. Assume that sailors are recruited in Cities A, B and C. The average salary of all sailors recruited in A is 80. Similarly, the average salary of all the sailors recruited at B is 82 and sailors recruited at C is 79. Since the highest average salary is 82, Franky will pay all the sailors in his fleet a salary of 82. Note that if no sailors are recruited from a given city, then the average salary of recruited sailors from that city is equal to 0.

Although a talented explorer and navigator, Franky is not familiar with optimization techniques. Hence, he has hired you to help him formulate a Dynamic Programming model to successfully hire 100 sailors at minimum cost (minimum total salary expenses). You can assume that in each city you visit, you are given a list of sailors that is ordered in increasing order of salaries. Hence, in city i you are given a list such that ni. for i=1,2,...,T.

Formulate a Dynamic Programming model to successfully hire 100 sailors at minimum cost (minimum total salary expenses).

Answer rating: 100% (QA)

To formulate a Dynamic Programming model to successfully hi... View the full answer