Perché l'approccio avido non funziona per il seguente problema, ma la soluzione fornita nell'editoriale funziona?

Question

Perché l'approccio avido non funziona per il seguente problema, ma la soluzione fornita nell'editoriale funziona?

#1 da (6 voti)

3

Dichiarazione di problemi:

Alexa ha due stack di numeri interi non negativi, stack A = [a0, a1,. . . , An_1] e impilare B = [b0, b1,. . . , bm_1] dove l'indice 0 indica la parte superiore della pila. Alexa sfida Nick a interpretare il seguente gioco:

In ogni mossa, Nick può rimuovere un intero dalla cima della pila A o della pila B. Nick mantiene una somma parziale dei numeri interi che rimuove dalle due pile. Nick viene squalificato dal gioco se, in qualsiasi momento, la sua somma parziale diventa maggiore di un intero dato all'inizio del gioco. Nick's fine / score è il numero totale di numeri interi che ha rimosso dai due stack. Dati i giochi A, B e m per g, trova il massimo punteggio possibile che Nick può ottenere (cioè il massimo numero di interi che può rimuovere senza essere squalificato)

Link al problema: link

La mia soluzione (approccio avido):

Seleziona (pop) l'elemento più piccolo tra quello presente in cima allo stack A e l'altro presente sopra lo stack B. Incrementa somma per il valore dell'elemento scoppiato e totale (numero di inti) per 1.
Ripeti 1 finché una somma diventa maggiore di quella richiesta o uno dei due stack si svuota.
Se uno dei due stack si svuota, salta fuori dall'altro stack fino a quando la somma corrente supera il limite richiesto.

Soluzione editoriale:

Questo problema può essere risolto in tempo lineare. Inizieremo prendendo il maggior numero possibile di interi dallo stack A senza eccedere la somma. Una volta fatto ciò inizieremo a prendere interi da B, ma ogni volta che la somma diventa più grande del limite, inseriremo nuovamente gli interi nello stack A. Assicurati di aggiornare la risposta (il numero di interi) come l'attraversamento attraverso lo stack B ha luogo. Interrompi il ciclo quando hai ripristinato tutti i numeri interi presi da A e non è possibile prendere più interi da B.

Spiega dove sto sbagliando e qual è l'intuizione dietro la soluzione editoriale?

data-structures algorithms stack

posta Sourabh Khandelwal 19.02.2017 - 21:35

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms stack

Struttura quando ho bisogno di più istanze di "copia" di una classe base comune? Design OOP: differenza tra due possibili soluzioni

score 6 · Accepted Answer

Considera il caso in cui il target è 6, A è [2, 2, 2] e B è [3, 1, 1, 1] . La soluzione qui è 4 ottenuta usando tutto B, ma la tua soluzione dà 3.

In generale gli algoritmi avidi non produrranno risultati ottimali nei casi in cui si suppone di guardare al futuro.

Per rispondere alla seconda parte della domanda: la descrizione editoriale è incompleta. Il passo importante che manca alla descrizione è di aggiornare la risposta solo quando l'hai migliorata . Il motivo per cui funziona è il seguente: puoi rappresentare ogni stato di gioco come due numeri: il numero di valori presi da A (chiamalo x ) e il numero di valori presi da B (chiamalo y ). Possiamo chiamare uno stato (x, y) valido se sommando i primi x valori di A e primi y i valori di B non superano qualche obiettivo. Possiamo chiamare uno stato (x, y) massimo se (x, y) è valido ma né (x + 1, y) né (x, y + 1) sono validi. Il punto chiave è quando massimizziamo x + y rispetto agli stati validi, quindi (x, y) deve essere massimale. Quindi possiamo ridurre il problema alla massimizzazione della somma degli stati massimi e al massimo di min(size(A), size(B) di questi.

La soluzione editoriale è molto semplice: enumera tutte le posizioni massime nel modo seguente: inizia a trovare x tale che (x, 0) sia massimo. Per ottenere il passaggio successivo, incrementa y e continua a diminuire di x fino a quando (x, y) è valido: sarà chiaramente anche il massimo. Interrompi quando y è troppo grande perché (0, y) sia valido. Quindi prendi questo elenco di% max coppie di% co_de (e ne avrai tutte) e prendi il massimo di (x, y) .

La soluzione editoriale capita di fondere gli step "enumera gli stati massimi" e "prendi il massimo delle loro somme", ma questa è un'ottimizzazione che non ne modifica la complessità.