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.

Improve this question
$\endgroup$
7
  • $\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, 2018 at 20:18
  • $\begingroup$ The whole round trip. So basically each round trip is double the distance from London $\endgroup$
    – user30599
    Sep 28, 2018 at 20:22
  • 7
    $\begingroup$ Isn’t this precisely the knapsack problem? $\endgroup$
    – Roman Odaisky
    Sep 28, 2018 at 20:27
  • 1
    $\begingroup$ Why put more than 15000 miles if there is nothing more than 15000 miles? $\endgroup$
    – PotatoLatte
    Sep 28, 2018 at 20:36
  • 1
    $\begingroup$ @PotatoLatte each trip must be a return direct trip from London, and each trip is a return, so the trip mileage is double the distance from London. $\endgroup$
    – user30599
    Sep 28, 2018 at 20:37

5 Answers 5

Reset to default
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.

Improve this answer
$\endgroup$
2
$\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$.

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ You have four cities with 2 culture points (I guess you forgot to count Reykjavik). This makes the total 50 points, just as the Jeep Scherphuis' answer. The only difference is that they used Tokyo + HK whereas you used Zanzibar + Wellington. $\endgroup$
    – PattuX
    Jul 19 at 11:03
1
$\begingroup$

As mentioned by @Roman Odaisky in a comment, this is an instance of the 0-1 knapsack problem. It turns out that there are 21 optimal solutions, all with objective value

50.

Others have posted optimal solutions but with no proof of optimality. It turns out that the linear programming relaxation (obtained by relaxing integrality) has optimal objective value

50.545064378,

and the corresponding dual variables provide a short certificate of optimality. Alternatively, it is well known that an optimal LP solution is obtained by sorting the items in descending order of value per weight.

Because the objective function has integer coefficients, the integer optimal value is at most the floor of the LP optimal value, so

50 is optimal.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.