Ois velox @ 10 / 100


#1

Salve a tutti,
Oggi ho provato a risolvere il problema “velox” delle ois2014.
Ottengo solo 10 punti, anche se sono quasi certo che la soluzione sia corretta… vorrei più che altro capire se è un problema di codice o se proprio la mia idea è sbagliata…
Qui c’è il mio codice {https://pastebin.com/0QnEuwT1}.
Grazie :smiley:


#2

Ciao, un esempio in cui il tuo programma sbaglia è il seguente:

4 3
0 1 100
1 2 20
2 3 50

Il percorso ottimale è 1-2-3 e quindi la risposta è 2, ma il tuo programma stampa 1.


#3

Con questo nuovo codice (https://pastebin.com/WRgDx6Tu) ottengo sempre 10/100 e il tuo esempio funziona correttamente.
Cosa mi consigli ?


#4

Devi affidarti alla programmazione dinamica.
Utilizzare il primo arco con velocità strettamente crescente a quella precedente che ti porta a un nodo non visitato non è sempre conveniente.

5 5
0 1 1
1 2 100
1 3 20
2 4 50
3 4 30 

Output 3 e non 2.


#5

Onestamente sono proprio a mare con la programmazione dinamica. Non la capisco proprio…
Mi aiuteresti ad entrare nella logica della DP con questo esercizio?


#6

Non sei l’unico xD Anch’io ho grandi difficoltà in questa tipologia di problemi.
Iniziare da velox per introdurre la programmazione dinamica per me è difficile come cosa, visto che ho usato un approccio abbastanza inusuale per risolverlo.
La programmazione dinamica consiste nel trovare la soluzione ottimale di un problema combinando le soluzioni ottimali dei sottoproblemi relativi ad esso.
Prendendo in considerazione velox in cui ci è richiesto di trovare il traggito più lungo con archi strettamente maggiori, il problema più grande è il traggitto completo mentre il relativo sottoproblema è il traggito più lungo relativo a un determinato arco.
Il sottoproblema del arco si ripete per ogni sua adiacenza e il problema relativo a ogni adiacenza si ripeterà per le adiacenze relative ad esso fin quando non potrai più usfruire di archi.
Il vantaggio della programmazione dinamica è proprio questo, combinare risultati già ottenuti senza doverli ricalcolare per ottenere il migliore.
Le difficoltà di questa tipologia sono molteplici, come trovare la struttura dati che contenga i risultati dei vari sottoproblemi e come ricavare tali soluzioni.
Esistono due approcci per risolvere questi problemi, top down e bottomup.
La top down (ricorsione) scompone il problema più grande in probelmi più piccoli facilmente risolvibili mentre la bottomup (iterativa) risolve problemi più piccoli per poi arrivare a quello più grande.
L’ apporccio da scegliere dipende soprattutto da come si ragiona e dalla natura del problema.
Io inizierei col risolvere i classici come poldo , sommelier e discesa massima. Per poi provare problemi semplici come number game , convegno aziendale e medaglie.
Credo di non essere stato chiarissimo ma ho fatto il meglio che potessi fare.
Se un utente più esperto ci vuole dare una mano ben vegna, ho solo da imparare.


#7

Grazie, apprezzo molto il tuo impegno nel cercare di introdurmi un argomento abbastanza complicato :slight_smile: