Come viene risolto il "problema del prelievo della pizza" utilizzando tecniche di programmazione dinamica?

Question

Come viene risolto il "problema del prelievo della pizza" utilizzando tecniche di programmazione dinamica?

#1 da (5 voti)
#2 da (3 voti)

9

Il problema di selezione della pizza di Winkler:

Una torta di pizza circolare di fette n , dove la porzione i ha l'area S_i i.e, l'area è diversa per ogni pezzo di torta.
Mangiato Alice e Bob a turno raccolgono le fette, ma è maleducato creare più spazi vuoti nella torta (non considerare consentito).
- Così ogni mangiatore è limitato a prendere una delle due fette adiacenti alla regione aperta. Alice va per prima, ed entrambi i mangiatori cercano più torta possibile.

In che modo un algoritmo di programmazione dinamica determina la quantità di torta che Alice mangia, se Alice e Bob giocano perfettamente per massimizzare il consumo di pizza?

Comprensione:

In un problema DP generale, andiamo avanti nella ricerca di sotto-problemi che possono essere visualizzati usando l'albero di ricorsione o, più strettamente, usando un DAG. Qui, non sto trovando alcun vantaggio per trovare i sotto-problemi qui.

Qui, per un dato set di S_i s, dobbiamo massimizzare l'area delle fette mangiate da Alice. Questo dipenderà dalla scelta di una permutazione di fette di Pizza da (n-1) permutazioni. Scegliendo una porzione di area massima tra due opzioni disponibili in ogni n \ 2 giri, Alice ottiene, ci darà l'area totale della fetta per una permutazione. Dobbiamo trovare l'area della fetta per tutte queste permutazioni. E poi il massimo da questi.

Qualcuno può darmi una mano su come andare avanti?

algorithms dynamic-programming

posta Amit Shekhar 31.10.2011 - 16:23

fonte

2 risposte

Leggi altre domande sui tag algorithms dynamic-programming

buoni libri su Scrum e XP [chiuso] che cosa conta come "esperienza" con un particolare linguaggio? [chiuso]

score 5 · Answer 1

Inizia considerando le fette appena posizionate su una fila e puoi scegliere tra una delle due estremità. In questo caso, supponendo che sia il tuo turno di scegliere, è chiaro che pizzaAmount(slices) è

Se non c'è la pizza, il risultato è 0
Se c'è un solo risultato di una fetta è quella sezione
Se ci sono almeno due sezioni, il risultato è:

(usando la sintassi Python)

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

In altre parole dovresti considerare entrambe le alternative e che dopo aver preso la tua fetta otterrai tutta la pizza rimanente eccetto il risultato della chiamata ricorsiva (perché il tuo amico userà la stessa strategia).

Puoi implementarlo con DP (o memoizing) perché la matrice è effettivamente fissa e puoi semplicemente considerare come parametri il primo e l'ultimo indice di sezione.

Per risolvere il problema completo originale devi solo provare tutte le sezioni come slice iniziale e scegliere quella che massimizza il risultato.

score 3 · Answer 2

Per una parte della pizza definisci F(i,j) come massimo quanto può mangiare la persona che prima preleva una fetta. Le fette di parte della pizza (i,j) sono:

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

Definisci R(i,j) (quanto rimasto per seconda persona) come 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) ),

Il massimo che Alice può mangiare è calcolato da:

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