How is the "Pizza picking problem‍​" solved using dynamic programming techniques?

Question

Winkler's pizza picking problem:

• A circular pizza pie of n slices, where slice i has area S_i i.e, the area is different for each pie piece.
• Eaters Alice and Bob take turns picking slices, but it is rude to create multiple gaps in the pie (consider it not allowed).
  • Thus each eater is restricted to taking one of the two slices adjacent to the open region. Alice goes first, and both eaters seek as much pie as possible.

How would a dynamic programming algorithm determine how much pie Alice eats, if both Alice and Bob play perfectly to maximize their pizza consumption?

My understanding:

In a general DP problem, we go forward with finding sub-problems which can be visualized using recursion tree or, more tightly, using a DAG. Here, I'm not finding any lead to find the sub-problems here.

Here, for a given set of S_i s, we need to maximize the area of slices eaten by Alice. This will depend on choosing a permutation of Pizza slices out of (n-1) permutations. Choosing a max area slice out of two options available in every n\2 turns Alice gets, will give us the total area of slice for a permutation. We need to find area of slice for all such permutations. And then the maximum out of these.

Can somebody help me out on how to go forward?

Answer 1

Start by considering the slices just placed on a row and you can pick from one of the two ends. In this case supposing it's your turn to chose it's clear that pizzaAmount(slices) is

1. If there's no pizza left result is 0
2. If there's only one slice result is that slice
3. If there are at least two slices then the result is:

(using Python syntax)

max(slices[0] + sum(slices[1:]) - pizzaAmount(slices[1:]),
    slices[-1] + sum(slices[:-1]) - pizzaAmount(slices[:-1]))

in other words you should consider both alternatives and that after taking your slice you will get all the remaining pizza except the result of the recursive call (because your friend will use the same strategy).

You can implement this with DP (or memoizing) because the array is indeed fixed and you can just consider as parameters the first and last slice index.

To solve the original full problem you just need to try all slices as starting slice and chose the one that maximizes the result.

Answer 2

For part of pizza define F(i,j) as maximum how much person that first picks slice can eat. Slices of part of pizza (i,j) are:

if i <= j than slices i, i+1, ..., j-1, j
if i > j than slices i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
and we don't define it for whole pizza, abs(i-j) < n-1

Define R(i,j) (how much left for second person) as sum(S_x, x in slices(i,j)) - F(i,j).

With:

F(i,i) = S_i,
F(i,j) = max( S_i + R(i+1,j), S_j + R(i,j-1) ),

maximum that Alice can eat is calculated by:

max( S_i + F(i+1, (i-1) if i > 1 else n) ).