I am doing a practice question from Midterm Dynamic Programming
The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an opponent, alternating turns. In each turn, a player selects either the first or last number, removes it from the row, and collects that much money.
For example, if the numbers are 1,2,3,4 , a possible game may look like:
- Player A takes 4: row is 1,2,3.
- Player B takes 3: row is 1,2.
- Player A takes 1: row is 2.
- Player B takes 2, game over.
Both players ended with a total amount of 5. Note that A could have done better.
(2 pts) Show an example where the greedy algorithm fails to achieve the highest possible amount of money.
The solution to this problem Greedy Sol used a solution list of number of [1,2,10,3]. However I would argue using the greedy algorithm, " In each turn, a player selects either the first or last" would work here to achieve the highest amount of money. Here is how I would work out the greedy algorithm
- Player A takes 1: row is 2, 10, 3.
- Player B takes 3: row is 2, 10.
- Player A takes 2: row is 10.
- Player B takes 10, game over.
And Player B has achieved the highest possible amount of money, 13.
Does everyone agree with my walkthrough and that the solution is wrong?
The solution I came up was 2, 8, 7, 6, 4. The idea I had here was that the highest amount of money could only be achieved by the player picking first(3 numbers).
For the player who picks first to achieve the highest possible amount of money. he or she would have to pick 8, 7, and 6. However with this greedy algorithm, that player in the first move either has to choose 2 or 4, meaning the highest possible amount of money is not achievable.(bc player 1 was the only player that could achieve the highest amount of money)