Seleziona la sequenza per minimizzare il costo

1

Diciamo che c'è un fattorino che vuole distribuire alcuni pacchetti di cibo in N città (1..N).

  • Conosciamo il numero Pi di pacchetti che devono essere consegnati in città i.

  • Conosciamo la distanza tra le città i e i + 1, sia d (i, i + 1).

  • Supponiamo anche che queste città siano in linea retta.

  • Conosciamo la velocità media V del ragazzo

  • E che tutti i pacchetti perdono valore con una tariffa specifica per unità di tempo.

  • Il ragazzo inizia dalla città J, 1 < = J < = N con tutti i pacchetti caricati.

Sto cercando di capire una soluzione usando DP per minimizzare il valore perso dei pacchetti di cibo.

Penso di aver trovato la sottostruttura ottimale del problema, con la seguente funzione ricorsiva, ma non posso davvero fare il passo successivo.

Se C (i, j) (noto dato il Pi-s e le distanze) è il costo di spostarsi da i a j, e opt (i) è la sequenza ottimale di arresti quando il ragazzo inizia dalla posizione i poi :

opt (K) = min (C (K, K + J) + opt (K + J), C (K, KJ) + opt (KJ)), con J selezionato per minimizzare entrambi gli argomenti di min ().

Penso di essere vicino. Aiutami con l'approccio per favore.

    
posta Learner 07.12.2015 - 20:09
fonte

0 risposte

Leggi altre domande sui tag