Requirement
Consider the following solitaire game: you are given a list of moves, x1, x2…xm, and their costs, y1, y2…ym. Moves and their costs both take the form of positive integers. Such a list of moves and their costs is called an instance of the game. To play the game, you start with a positive integer n. On each turn of the game you have two choices: subtract 1 from n incurring a cost of 1 or pick some move xi such that n is divisible by xi and divide n by xi incurring a cost of yi. The goal is to get to 0 while incurring the minimum possible cost.
- Divide 20 by 4 to get 5, incurring a cost of 1
- Subtract 1 from 5 to get 4 incurring a cost of 1
- Divide 4 by 4 to get 1, incurring a cost of 1
- Subtract 1 from 1 to get 0, incurring a cost of 1
So the final cost is 4. One suboptimal strategy for this game is as follows:
- Divide 20 by 5 to get 4, incurring a cost of 3
- Divide 4 by 4 to get 1, incurring a cost of 1
- Subtract 1 from 1 to get 0, incurring a cost of 1
which gives us a total cost of 5.
One possible greedy algorithm for this game is as follows: On each turn, simply divide the current number by the legal move x of cost y which maximizes x / y - the ratio of move to cost (and subtract 1 from the current number if it is not divisible by any move). If two legal moves have the same ratio of move to cost then the greedy algorithm will take the larger move. Unfortunately, this greedy algorithm does not always give the optimal strategy. In this problem you will find counterexamples that show the greedy algorithm is not optimal in different instances of this game.
Tips
To find instances where the greedy algorithm fails, you will probably need to be able to find the optimal strategy in all instances. What kind of algorithm can you use to do this?
Most of the difficulty of this request is in coming up with the right approach. The code you write does not need to be especially long or complex to solve the problem.
It may take some time for your code to find a counterexample, particularly for the last couple instances. But if it takes more than a couple of minutes, you probably need to rethink your approach.
When searching for instances of where the greedy algorithm fails, it is useful to avoid redoing work.
For reference, the optimal cost for the instance (3, 1), (2, 1) when n is 321 is 10, and the greedy algorithm gives 11. The smallest value of n for which the greedy algorithm fails on the instance (211, 2), (210, 1) is 4740960.
Start early. You have two weeks to do this problem, so you shouldn’t try to do it all in the last day.