1
$\begingroup$

This isn't my own creation, it's an exercise that my partner had to do during a work exercise and seemed interesting to share here.

You've been given 86,400 Air Miles to explore the world and there's a list of destinations which you can visit.

You win Culture Points for each round trip that forms part of the challenge. Each trip must be a return trip from London.

Below is a list of each country with the distance from London

Berlin - 570 miles
Bombay - 4660
Buenos Aires - 6920
Cape Town - 6010
Darwin - 8600
Hong Kong - 5980
Istanbul - 1550
Juneau (Alaska) - 4420
Manila - 6670
Mexico City - 5540
Moscow - 1550
New York - 3460
Oslo - 710
Paris - 210
Port Said - 2150
Quebec - 3100
Reykjavik - 1170
Rio de Janeiro - 5770
Rome - 890
Shanghai - 5710
Tokyo - 5940
Wellington - 11680
Zanzibar City - 4600

Culture points are as follows:

0 - 1000 miles - 1 Culture point
1001 - 3000 miles - 2 Culture points
3001 - 6000 miles - 3 Culture points
6001 - 10,000 miles - 4 Culture points
10,001 - 15,000 - 5 Culture points
More than 15,001 miles - 6 culture points

If you're allowed to make the same trip more than once, the optimal strategy is of course repeating the trip to Paris.

However, with the constraint that you can only make each trip once, what is the optimal strategy for earning the most Culture points?

Please feel tree to re-tag this question, I'm not sure what the most appropriate tags are for this one.

$\endgroup$
  • $\begingroup$ Do the air miles it costs and the culture points it earns based on each way or for the whole round trip. For example, would it cost 710 air miles and earn one culture point for Oslo or would it be 1420 air miles and earn 2? Also you put Berlin twice accidentally. $\endgroup$ – gabbo1092 Sep 28 '18 at 20:18
  • $\begingroup$ The whole round trip. So basically each round trip is double the distance from London $\endgroup$ – Snow Sep 28 '18 at 20:22
  • $\begingroup$ Do you have to go round trip? Can you go from London to Paris to Oslo and then back to London? $\endgroup$ – PotatoLatte Sep 28 '18 at 20:27
  • 5
    $\begingroup$ Isn’t this precisely the knapsack problem? $\endgroup$ – Roman Odaisky Sep 28 '18 at 20:27
  • 1
    $\begingroup$ Why put more than 15000 miles if there is nothing more than 15000 miles? $\endgroup$ – PotatoLatte Sep 28 '18 at 20:36
4
$\begingroup$

As far as I can tell this is the best answer:

50 Culture Points - 85480 miles travelled. This is lower than before because I realised I had a math error.

Places visited:

Paris, Berlin, Oslo, Rome, Reykjavik, Moscow, Istanbul, Port Said, Quebec, New York, Bombay, Mexico City, Shanghai, Rio de Janeiro, Tokyo.

$\endgroup$
3
$\begingroup$

The best answer is

50

culture points, which agrees with gabbo1092's answer.

Here's the explanation:

Sort the list of cities by their round trip length. Then sum the distances, starting from the nearest. Stop when the total exceeds 86400 miles

 City             Dist Pts   Sum1    Sum2
 ----------------------------------------
 Paris             420   1    420     420
 
 Berlin           1140   2   1560    1560
 Oslo             1420       2980    2980
 Rome             1780       4760    4760
 Reykjavik        2340       7100    7100
 
 Istanbul         3100   3  10200   10200
 Moscow           3100      13300   13300
 Port Said        4300      17600   17600
 
 Quebec           6200   4  23800   23800
 New York         6920      30720   30720
 Juneau (Alaska)  8840      39560   39560
 Zanzibar City    9200      48760       -
 Bombay           9320      58080       -
 
 Mexico City     11080   5  69160   50640
 Shanghai        11420      80580   62060
 Rio de Janeiro  11540              73600
 Tokyo           11880              85480
 Hong Kong       11960
 Cape Town       12020
 Manila          13340
 Buenos Aires    13840
 
 Darwin          19200   6
 Wellington      23360
This gives the column marked Sum1. The sum is $80580$, leaving almost $6000$ spare air miles. This is not enough to upgrade a 3-point city to a 5-point one, but we can upgrade two of the 4-point cities to 5-point cities. This is shown in the Sum2 column. There are only $920$ spare air miles left so no further upgrades are possible, but there is a little freedom to choose which three 4-point and which four 5-point cities to visit.

The number of points is $1*1+4*2+3*3+3*4+4*5 = 1+8+9+12+20 = 50$.

$\endgroup$
1
$\begingroup$

I think the goal is to

minimize your miles per culture point.

So,

total miles per culture point, from smallest to greatest, is
Paris - 420 / 1 = 420
Berlin - 1140 miles / 2 = 570
Oslo - 1420 / 2 = 710
Rome - 1780 / 2 = 890
Istanbul - 3100 / 3 = 1033.33
Moscow - 3100 / 3 = 1033.33
Reykjavik - 2340 / 2 = 1170
Port Said - 4300 / 3 = 1433.33
Quebec - 6200 / 4 = 1550
New York - 6920 / 4 = 1730
Juneau (Alaska) - 8840 / 4 = 2210
Mexico City - 11080 / 5 = 2216
Shanghai - 11420 / 5 = 2284
Zanzibar City - 9200 / 4 = 2300
Rio de Janeiro - 11540 / 5 = 2308
Bombay - 9320 / 4 = 2330
Tokyo - 11880 / 5 = 2376
Hong Kong - 11960 / 5 = 2392
Cape Town - 12020 / 5 = 2404
Manila - 13340 / 5 = 2668
Buenos Aires - 13840 / 5 = 2768
Darwin - 17200 / 6 = 2866.66
Wellington - 23360 / 6 = 3893.33

Subject to the constraint that the total sum of the miles can’t exceed 86400.

So

Paris + Berlin + Oslo + Rome + Istanbul + Moscow + Reykjavik + Port Said + Quebec + New York + Juneau + Mexico City + Shanghai + Zanzibar + Darwin = 420 + 1140 + 1420 + 1780 + 3100 + 3100 + 4300 + 6200 + 6920 + 8840 + 11080 + 11420 + 9200 + 17200 = 86120.

We notice that we included

Darwin at the end to maximize our points with the minimized cap room. This gives $1 + 3(2) + 3(3) + 4(4) + 2(5) + 6 = 48$ culture points.

$\endgroup$
0
$\begingroup$

The best I have gotten so far is:

43 Points by traveling from smallest round trip to largest round trip until I ran out of miles.

I tried another approach to take the smallest round trips in each category until I couldn't afford that category anymore and I ended up with:

41 Points.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.