# Air Miles Challenge

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
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.

• 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. Sep 28, 2018 at 20:18
• The whole round trip. So basically each round trip is double the distance from London
– user30599
Sep 28, 2018 at 20:22
• Isn’t this precisely the knapsack problem? Sep 28, 2018 at 20:27
• Why put more than 15000 miles if there is nothing more than 15000 miles? Sep 28, 2018 at 20:36
• @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.
– user30599
Sep 28, 2018 at 20:37

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.

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
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$$.

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.

• 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. Jul 19 at 11:03

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.

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.