Comment le «problème de préparation de pizza» est-il résolu en utilisant des techniques de programmation dynamique?

Problème de cueillette de pizza de Winkler:

• Une tarte à pizza circulaire de ntranches, où la tranche ia une zone, S_ic'est-à-dire que la zone est différente pour chaque morceau de tarte.
• Les mangeurs Alice et Bob choisissent à tour de rôle des tranches, mais il est impoli de créer plusieurs lacunes dans la tarte (considérez que ce n'est pas autorisé).
  • Ainsi, chaque mangeur est limité à prendre l'une des deux tranches adjacentes à la région ouverte. Alice va en premier, et les deux mangeurs cherchent autant de tarte que possible.

Comment un algorithme de programmation dynamique déterminerait-il combien de tarte Alice mange, si Alice et Bob jouent parfaitement pour maximiser leur consommation de pizza?

Ma compréhension:

Dans un problème DP général, nous allons de l'avant avec la recherche de sous-problèmes qui peuvent être visualisés à l'aide d'un arbre de récursivité ou, plus précisément, à l'aide d'un DAG. Ici, je ne trouve aucune piste pour trouver les sous-problèmes ici.

Ici, pour un ensemble donné de S_i s, nous devons maximiser la surface des tranches consommées par Alice. Cela dépendra du choix d'une permutation de tranches de pizza parmi (n-1) permutations. Choisir une tranche de zone maximale parmi deux options disponibles à chaque n \ 2 tours qu'Alice obtient, nous donnera la zone totale de tranche pour une permutation. Nous devons trouver une zone de tranche pour toutes ces permutations. Et puis le maximum de ceux-ci.

Quelqu'un peut-il m'aider à avancer?

Commencez par considérer les tranches juste placées sur une rangée et vous pouvez choisir l'une des deux extrémités. Dans ce cas , en supposant que votre tour de choisir , il est clair que pizzaAmount(slices)est

1. S'il n'y a plus de pizza, le résultat est 0
2. S'il n'y a qu'un seul résultat de tranche est cette tranche
3. S'il y a au moins deux tranches, le résultat est:

(en utilisant la syntaxe Python)

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

en d'autres termes, vous devriez considérer les deux alternatives et qu'après avoir pris votre tranche, vous obtiendrez toute la pizza restante, sauf le résultat de l'appel récursif (car votre ami utilisera la même stratégie).

Vous pouvez l'implémenter avec DP (ou mémorisation) car le tableau est en effet fixe et vous pouvez simplement considérer comme paramètres le premier et le dernier index de tranche.

Pour résoudre le problème complet d'origine, il vous suffit d'essayer toutes les tranches comme tranche de départ et de choisir celle qui maximise le résultat.

Pour une partie de la pizza, définissez F(i,j)la quantité maximale que la personne qui choisit la première tranche peut manger. Les tranches de pizza (i,j)sont:

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

Définissez R(i,j)(combien il reste pour la deuxième personne) comme sum(S_x, x in slices(i,j)) - F(i,j).

Avec:

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

maximum qu'Alice peut manger est calculé par:

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