Algoritmo per determinare il massimo divertimento

Question

Il problema si può trovare here. Il nocciolo della questione è che Bessie sta cavalcando un ottovolante, ma le vengono le vertigini. Qual è la quantità massima di divertimento che può avere senza superare il suo "limite vertiginoso". L'ingresso è costituito da:

"NKL

dove N (1 ≤ N ≤ 1,000) è il numero di sezioni di questo particolare ottovolante; K (1 ≤ k ≤ 500) è l'importo che il livello di vertigini di Bessies diminuirà se tiene gli occhi chiusi su qualsiasi sezione della corsa, e L (1 ≤ L ≤ 300.000) è il limite di vertigini che Bessie può tollerare - se le sue vertigini diventano mai più grandi di L, Bessie si ammalano e questo non è divertente!

Ciascuna delle successive righe N avrà due numeri interi:

FD

dove F (1 ≤ F ≤ 20) è l'aumento a Bessies divertimento totale che la Shell ottenere se lei tiene gli occhi aperti su quella sezione, e D (1 ≤ D ≤ 500) è l'aumento al suo livello di vertigine se lei tiene gli occhi aperti su quella sezione. Le sezioni saranno elencati in ordine "

mio algoritmo per risolvere questo assomiglia a questo:..?

 cin >> N; // sections 
     cin >> K; // amount dizziness can go down 
     cin >> L; // dizzy ceiling 
     belowL = L; // sets the amount of dizzy left 

     for (int i = 0; i < N; i++) { 
      cout << "\n" << i; 
      cin >> F >> D; // fun increase and dizzy increase 
      if (D < belowL) { 
       if (F >= D) { 
        funTotal += F; 
       } 
      } 
      else { 
       belowL -= K; 
      } 

Tuttavia, questo non sempre cedere il risultato corretto Qual è il problema Si deve scegliere l'opzione di divertimento, a meno che non avrebbe messo Bessie oltre la soglia malattia. c'è un modo migliore per farlo?

Answer 1

Quindi piuttosto che fornire codice qui è una sorta di spiegazione della soluzione del problema.

L'approccio di base è risolvere utilizzando la programmazione dinamica poiché ciò si riduce a ciò che viene chiamato Knapsack problem.Pensaci in questo modo, le sue vertigini sono quanto riesce a portare nel sacco in una volta e il divertimento è ciò che vorrebbe massimizzare (rispetto al valore degli "oggetti" che porta in un sacco). Ora quello che vorremmo fare è ottenere il massimo divertimento dalle montagne russe (la maggior parte del valore nel sacco) senza farle girare le vertigini (superando il limite di "peso" sul sacco).

Quindi ora vuoi scegliere quali parti ha gli occhi aperti/chiusi (se un oggetto è nel sacco o no). Quindi un modo semplice per pensare a questo è scegliere il massimo di entrambe le opzioni. Se riesce a tenere gli occhi aperti senza superare la soglia o se tenere gli occhi chiusi. Ma ora il problema cambia, si vede se lei tiene gli occhi aperti la sua soglia di diziness diminuirà (più facile da risolvere sub problemi).

Utilizzando queste informazioni diventa facile adattare la soluzione zaino a questo problema senza dover ricorrere a backtracking o ricorsione.

L'idea è di salvare tutti i sottoproblemi precedentemente risolti in una matrice in modo da poter riutilizzare i risultati anziché ricalcolarli ogni volta. Nota un trucco che puoi usare è che hai solo bisogno della riga corrente della matrice e quella precedentemente risolta perché la relazione di ricorrenza per lo zaino richiede solo quelle voci :)

PS Ero nella regione in cui questo problema è stato dato e Risolto, bello vedere di nuovo questo problema

Answer 2

occorre scegliere l'opzione di divertimento, a meno che non avrebbe messo Bessie oltre la soglia malattia. c'è un modo migliore per fare tha t?

Il problema è che non stai massimizzando il divertimento qui, stai solo impedendo a Bessie di ammalarsi. Quando arrivi a una sezione che la metterebbe al di sopra del limite di vertigini, potresti essere in grado di aggiungere più divertimento tornando indietro e prendendo l'opzione non divertente in qualche sezione precedente. Diciamo che hai di input come questo, in F D ordine:

1 400 
5 450 
10 25 
18 75 
20 400 

Inoltre, diciamo che lei è già vicino al limite vertigini, quando colpisce la prima sezione di cui sopra. Potresti prendere l'opzione divertente nelle prime due sezioni e ottenere un aumento F di 6 e un aumento di D di 850. Forse questo la mette al limite. Ora non hai altra scelta che prendere l'opzione non divertente per le sezioni successive. D'altra parte, se prendi l'opzione non-divertente per le prime due sezioni, puoi prendere l'opzione divertente per i prossimi tre e ottenere un aumento di F di 48 per un aumento di D di soli 500.

l'algoritmo corrente prende l'opzione divertente se il rapporto F: D è maggiore di 1 e hai abbastanza capacità di vertigini rimaste. È ragionevole, ma non ottimale. È probabile che nessun rapporto fisso fornisca una soluzione ottimale. Invece, è necessario considerare il beneficio e il costo di ciascuna opzione per ogni sezione.