# How is the “Pizza picking problem‍​” solved using dynamic programming techniques?

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?

## 2 Answers

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 + 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.

• Thanks "6502". I can visualise the problem better by utilising the hint of "considering the slices just placed on a row and picking from one of the two ends". Given recurrence relation is taking care of the optimal choice by the opponent, as well. I'll post a formal algorithm soon. Thanks guys!! – ami Oct 31 '11 at 22:52
• Just curious, what is the order of complexity for this algorithm? 0(n * 2^n)? – Akron Oct 31 '11 at 23:28
• @Akron: This is what it would be without a dynamic programming approach or memoization. However you can take advantage of the fact that the result of `pizzaAmount` does depends only on what are the start and stop index of the remaining slices and not on the sequence of which pizza slices you and your friend already ate so you can store the result in a matrix to avoid recomputation. The order of the algorithm is therefore O(n**2). – 6502 Nov 1 '11 at 6:22
• If anyone is still struggling to understand, this link has a very nice explanation. – Amit Shekhar Mar 3 '12 at 22:35

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) ).
``````