Algoritmo del campo di addestramento

Question

Algoritmo del campo di addestramento

#1 da (2 voti)
#2 da (1 voti)

5

Dichiarazione del problema -

L'obiettivo è trovare il segmento di test contiguo più redditizio, data una sequenza di punteggi di test, con la possibilità di eliminare qualsiasi test k da un intervallo scelto.

Il problema sembra essere un problema DP all'inizio, ma la complessità si presenta quando la condizione di caduta del test entra nell'immagine.

Quali modifiche possono essere apportate al classico approccio DP per questo problema? O c'è un approccio completamente diverso?

Intervallo di prova - N < = 10 ⁴

Fonte - Documento Q INOI 2011

algorithms dynamic-programming

posta 7Aces 24.12.2012 - 14:40

fonte

2 risposte

Leggi altre domande sui tag algorithms dynamic-programming

Come dovrei organizzare bug in redmine? Relazione tra "Task Parallel Library" e "Task Asynchronous Pattern"?

score 2 · Answer 1

Bene, ecco come lo farei (senza entrare troppo nei dettagli)

Vorrei tenere traccia del valore di tutti i risultati che ho lasciato. Probabilmente li inserirò in una coda ordinata la cui dimensione è il numero consentito di test saltati. Sarebbe classificato come il test caduto più vicino allo zero è all'inizio. Mentre passo alla lista con l'algoritmo tradizionale, farei quanto segue:

if I encounter a negative number
    if the queue is not full
        add it to the queue
    else
        if the new negative number is smaller (farther from zero) than the first number in the queue
            remove the first number from the queue
            add the new number to the queue
            add the removed number to the current subsequence value
        else
            add the new negative number to the current subsequence value

In questo modo, si mantiene sempre la sottosequenza senza il segno peggiore della sequenza e se si incontra un segno ancora peggiore, è possibile ripristinare il valore di un segno precedentemente abbandonato sul valore della sottosequenza.

score 1 · Answer 2

L'algoritmo originale è fondamentalmente:

for each position:
    calculate best range ending at this position
print best over all possible ending positions

Il miglior intervallo possibile che termina in una posizione è il massimo di:

0 (iniziando da zero qui)
il miglior intervallo possibile della posizione precedente + nuovo segno

Ora, dobbiamo calcolare le conclusioni di K, per quantità diverse di test rilasciati

for each position:
    for k = 0 to K:
        calculate best possible range ending at this position and dropping at most k tests
print best of all calculated ranges

Il miglior intervallo possibile è il massimo di:

0 (inizia un nuovo intervallo in questa posizione)
il miglior intervallo possibile della posizione precedente + nuovo segno
il miglior intervallo possibile della posizione precedente e un test meno abbattuto