Wie wird das „Pizza Picking Problem“ mit dynamischen Programmiertechniken gelöst?

Winklers Problem beim Pizzasammeln:

• Eine kreisförmige Pizzakuchenscheibe n, bei der die Scheibe ieine Fläche hat, S_idh die Fläche ist für jedes Tortenstück unterschiedlich.
• Die Esser Alice und Bob pflücken abwechselnd Scheiben, aber es ist unhöflich, mehrere Lücken in der Torte zu schaffen (betrachten Sie es als nicht erlaubt).
  • Somit ist jeder Esser darauf beschränkt, eine der beiden Scheiben neben dem offenen Bereich zu nehmen. Alice geht zuerst und beide Esser suchen so viel Kuchen wie möglich.

Wie würde ein dynamischer Programmieralgorithmus bestimmen, wie viel Kuchen Alice isst, wenn sowohl Alice als auch Bob perfekt spielen, um ihren Pizzakonsum zu maximieren?

Mein Verständnis:

In einem allgemeinen DP-Problem suchen wir nach Unterproblemen, die mithilfe eines Rekursionsbaums oder genauer gesagt mithilfe einer DAG visualisiert werden können. Hier finde ich keinen Anhaltspunkt, um die Unterprobleme hier zu finden.

Hier müssen wir für einen gegebenen Satz von S_i s die Fläche der von Alice verzehrten Scheiben maximieren. Dies hängt von der Auswahl einer Permutation von Pizzastücken aus (n-1) Permutationen ab. Wenn Sie aus zwei Optionen, die Alice in jeder n \ 2 Runde erhält, ein Slice mit maximaler Fläche auswählen, erhalten Sie die Gesamtfläche des Slice für eine Permutation. Für all diese Permutationen müssen wir einen Slice-Bereich finden. Und dann das Maximum aus diesen.

Kann mir jemand helfen, wie ich vorgehen soll?

Betrachten Sie zunächst die Scheiben, die gerade in einer Reihe platziert wurden, und wählen Sie eines der beiden Enden aus. Angenommen, Sie sind an der Reihe, zu entscheiden, ob dies klar pizzaAmount(slices)ist

1. Wenn keine Pizza mehr übrig ist, ist das Ergebnis 0
2. Wenn es nur ein Slice-Ergebnis gibt, ist dieses Slice
3. Wenn mindestens zwei Scheiben vorhanden sind, lautet das Ergebnis:

(mit Python-Syntax)

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

Mit anderen Worten, Sie sollten beide Alternativen in Betracht ziehen und dass Sie nach der Einnahme Ihres Stücks die gesamte verbleibende Pizza mit Ausnahme des Ergebnisses des rekursiven Aufrufs erhalten (da Ihr Freund dieselbe Strategie verwendet).

Sie können dies mit DP (oder Memoizing) implementieren, da das Array tatsächlich fest ist und Sie nur den ersten und den letzten Slice-Index als Parameter betrachten können.

Um das ursprüngliche vollständige Problem zu lösen, müssen Sie nur alle Slices als Start-Slice ausprobieren und das auswählen, das das Ergebnis maximiert.

Definieren Sie für einen Teil der Pizza F(i,j)als Maximum, wie viel Person, die zuerst ein Stück auswählt, essen kann. Teile eines Teils der Pizza (i,j)sind:

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

Definieren Sie R(i,j)(wie viel für die zweite Person übrig ist) als sum(S_x, x in slices(i,j)) - F(i,j).

Mit:

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

Das Maximum, das Alice essen kann, wird berechnet durch:

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