We are designing an Amazing Race course. Contestants will travel back and forth
between various cities. We want to choose the required sequence of cities
so that the total effort of a contestant is as close as possible to
1000.
The total effort of a contestant is the sum of the effort
for each city-to-city trip, but the effort for a trip depends on how tired
the contestant is. Let effort(c1,c2) be the effort required to travel from city c1
to city c2 when a contestant is fresh. We estimate that if the contestant has
already completed k trips then the effort required for a trip from city c1 to
city c2 is
factork * effort(c1,c2)
where factor is a fixed value >= 1.
Create a class Amazing that contains a method totalE that is given factor,
numTrips, and a String[] effort. Each element of effort contains a single space separated list of integers. The jth integer in the ith element of effort is effort(ci,cj). Your method should find the race course with exactly numTrips trips that comes closest to requiring a total effort of 1000, and return the absolute difference between that total effort and 1000.
A trip may go from a city to itself, and effort(ci,ci) is not necessarily 0.
|