2
$\begingroup$

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:

  1. Player A takes 4: row is 1,2,3.
  2. Player B takes 3: row is 1,2.
  3. Player A takes 1: row is 2.
  4. 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

  1. Player A takes 1: row is 2, 10, 3.
  2. Player B takes 3: row is 2, 10.
  3. Player A takes 2: row is 10.
  4. 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)

$\endgroup$
  • 1
    $\begingroup$ The greedy algorithm says "take the larger of first or last", so in that example, per the greedy algorithm, $A$ would first take $3$, making $10$ accessible to $B$. Taking either first or last is the rule of the game. $\endgroup$ – Daniel Fischer May 6 '15 at 19:43
  • $\begingroup$ The point of the solution is that if A uses the greedy algorithm, A will not achieve the optimal payout. Forget about B's strategy and payout. $\endgroup$ – vadim123 May 6 '15 at 19:44
  • $\begingroup$ @vadim123 Wouldn't you have to consider that A or B could achieve the optimal payout? $\endgroup$ – committedandroider May 6 '15 at 19:48
  • $\begingroup$ @DanielFischer So Just to make sure with [1, 2, 3, 4], the greedy algorithm will also not achieve the optimal payout? $\endgroup$ – committedandroider May 6 '15 at 19:50
  • $\begingroup$ For [1,2,3,4], the greedy algorithm works, if $B$ plays well, the $6$ that the greedy algorithm gives $A$ is optimal. $\endgroup$ – Daniel Fischer May 6 '15 at 19:54
1
$\begingroup$

What happened here was, thanks to @DanielFischer comment, I confused the definition of greedy algorithm and the actual rules of the game.

A greedy algorithm is one that "looks for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit." Greedy 1 Def and doing so "without worrying about the effect these decisions may have in the future." Greedy 2 Def.

Based on those two definitions and the rules of the game, the greedy algorithm here would be "take the larger of first or last"(@DanielFischer's comment")

Working that greedy algorithm with an input of [1, 2, 10, 3], player A would first choose 3 and player B would then choose 10. Because 10 and 3 need to be chosen by the same player to reach the highest payment, the greedy algorithm fails to achieve the highest possible amount of money

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.