Winkler's pizza picking problem:
- A circular pizza pie of
nslices, where slice
S_ii.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?
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?