¿Cómo se resuelve el "problema de recolección de pizza‍" utilizando técnicas de programación dinámica?

Problema de recolección de pizza de Winkler:

• Una tarta circular de nrebanadas de pizza , donde la rebanada itiene área S_i, es decir, el área es diferente para cada trozo de tarta.
• Los comedores Alice y Bob se turnan para recoger rebanadas, pero es grosero crear múltiples huecos en el pastel (considere que no está permitido).
  • Por lo tanto, cada comedor está restringido a tomar una de las dos rebanadas adyacentes a la región abierta. Alice va primero, y ambos comedores buscan la mayor cantidad de pastel posible.

¿Cómo determinaría un algoritmo de programación dinámica cuánto pastel come Alice, si tanto Alice como Bob juegan perfectamente para maximizar su consumo de pizza?

Mi punto de vista:

En un problema general de DP, seguimos encontrando subproblemas que se pueden visualizar usando el árbol de recursión o, más estrictamente, usando un DAG. Aquí, no encuentro ninguna pista para encontrar los subproblemas aquí.

Aquí, para un conjunto dado de S_i s, necesitamos maximizar el área de rebanadas que come Alice. Esto dependerá de elegir una permutación de porciones de Pizza de (n-1) permutaciones. Elegir una porción de área máxima de dos opciones disponibles en cada n \ 2 turnos que obtiene Alice nos dará el área total de porción para una permutación. Necesitamos encontrar el área de corte para todas esas permutaciones. Y luego el máximo de estos.

¿Alguien puede ayudarme a seguir adelante?

Comience considerando las rebanadas que se acaban de colocar en una fila y puede elegir uno de los dos extremos. En este caso, suponiendo que sea tu turno de elegir, está claro que pizzaAmount(slices)es

1. Si no queda pizza, el resultado es 0
2. Si solo hay un resultado de corte es ese corte
3. Si hay al menos dos rebanadas, el resultado es:

(usando la sintaxis de Python)

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

en otras palabras, debe considerar ambas alternativas y que después de tomar su porción obtendrá toda la pizza restante, excepto el resultado de la llamada recursiva (porque su amigo usará la misma estrategia).

Puede implementar esto con DP (o memorando) porque la matriz es realmente fija y solo puede considerar como parámetros el primer y último índice de segmento.

Para resolver el problema original completo solo necesita probar todos los cortes como el corte inicial y elegir el que maximice el resultado.

Para parte de la pizza, defina F(i,j)como máximo cuánta persona puede comer la primera rebanada. Las porciones de parte de la pizza (i,j)son:

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

Definir R(i,j)(cuánto queda para la segunda persona) como sum(S_x, x in slices(i,j)) - F(i,j).

Con:

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

El máximo que Alice puede comer se calcula mediante:

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