LC: Campus Bikes II - spiralgo/algorithms GitHub Wiki

Campus Bikes II

The Essence:

Making local, greedy decisions won't work here. This is because the total some can always be smaller for another. The best possible option is then trying all the possible permutations of workers and bikes. This would actually lead to a factorial computational complexity, since there are multiplying, permutational decisions made at each level. However, many decision are being repetitively made.

For this, one can perhaps store partial-decision made and reuse them if they come across again. The decision for matching workers to the last 2 of 5 bikes can be saved for example, and then reused again.

Details:

Saving partial decisions can be done by keeping an array that stores the distance for that particular decision. This can be implemented by interpreting the decision as a binary mask, with 1 and 0 bits representing if a bike has been taken or not. The rest of the decision process can be implemented using recursion.

Further explanation and the code can be found here: https://github.com/spiralgo/algorithms/pull/275