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

Here is the solution to the problem Greedy Sol enter image description here

In the diagram, does anyone know where the 11, the root of the tree, is coming from? I thought it was the highest possible amount of money but that be 13 here (10 + 3).

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If I understand correctly, this diagram represents both players playing optimally. Every value inside the node(rectangle/circle) is the highest possible value the first play can obtain if both players play optimally. After the first step of the first player, there are two possible states {2,10,3} and {1,2,10}. In {1,2,10} it is the second player's turn and if she/he plays optimally, the highest value the first player can obtain is 2 (the second player will remove 10 first to be optimal). However, if the first player remove 1 first (thus the state {2,10,3}), then no matter how the second player remove next, the first player will remove 10 in her/his second turn to be optimal. Thus highest value the first player can obtain is $$\max\{3 + 2, 1 + 10\}=11$$

$\endgroup$
3
  • $\begingroup$ +1: Excellent observation! I think, though, that the values in the rectangles indicate the highest value the second player can obtain from that point (again, assuming that both are playing optimally). $\endgroup$
    – Cameron Buie
    May 7, 2015 at 2:22
  • 1
    $\begingroup$ @CameronBuie No. When it is a rectangle, it is the second player's turn to remove a value. For example, since leaves are all second player's turns, their values are 0 for the first player. $\endgroup$
    – PSPACEhard
    May 7, 2015 at 2:30
  • $\begingroup$ /shakes head/ Right you are! Looks like it's my bedtime. :-\ $\endgroup$
    – Cameron Buie
    May 7, 2015 at 2:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .