[Algoritmi] Esercizio: soluzione alternativa alla memoizzazione

[absinth]

Ciao a tutti! Sto svolgendo un esercizio la cui soluzione proposta è la memoizzazione (tecnica a me sconosciuta) ma non voglio farvela vedere perché mi interessa capire se la mia idea può andare anche se non è altrettanto efficiente dal punto di vista delle prestazioni temporali.

Consegna:
Per comprarvi l’ultimo gadget tecnologico, avete pazientemente risparmiato inserendo monete in un salvadanaio. Purtroppo, non avete tenuto i conti, e non sapete quanti soldi ci sono dentro. E’ facile ottenere il valore totale rompendo il salvadanaio, ma sarebbe un peccato romperlo senza essere sicuri che ci siano abbastanza soldi per il vostro gadget.
Fortunatamente, siete informatici e avete a disposizione le seguenti informazioni: il peso totale T delle monete contenute nel salvadanaio, più il vettore dei pesi p[1 . . . n] e dei valori v[1 . . . n], dove p e il peso in grammi è v e il valore in centesimi dell'i-esimo tipo di moneta fra gli n tipi di monete prodotti nel vostro stato.
Scrivere un algoritmo che restituisca il minimo valore in centesimi che può essere contenuto nel salvadanaio, e valutarne la complessità.
Ad esempio, supponete che il peso totale sia 50 grammi, e le monete a disposizione siano quella da 200 centesimi che pesa 50 grammi, e quella da 50 centesimi che pesa 10 grammi. E’ possibile ottenere i 50 grammi del peso totale con una singola moneta da 200 centesimi, o con 5 da 50 centesimi per un totale di 250 centesimi. Quindi il valore da restituire è 200, che e il minimo fra i due totali.

Soluzione mia:
Io ho pensato di creare una classe chiamata: moneta che contiene sia il prezzo che il peso per ogni $i$. Ora creo un array di oggetti "moneta[]". Gli oggetti moneta li rendo comparable in base al seguente criterio: moneta.compareTo(moneta[j])<0 se v/p

Cita

Segnala

---

Risposte

apatriarca

7 set 2017, 13:25

La memoizzazione consiste semplicemente nel memorizzare il valore di una funzione in modo che quando viene nuovamente chiamata con lo stesso argomento venga restituito il valore direttamente invece di doverlo ricalcolare. Il problema ha tutto l'aspetto di essere uno di programmazione dinamica. Non mi è comunque del tutto chiaro il tuo procedimento (anche se non mi sembra tu possa fare ricorso alla memoizzazione da quello che ho capito nel tuo procedimento). Prova a scriverlo come pseudocodice e poi vediamo.

Cita

Segnala

---

Rispondi

Per rispondere a questa discussione devi prima effettuare il login.

[apatriarca]

La memoizzazione consiste semplicemente nel memorizzare il valore di una funzione in modo che quando viene nuovamente chiamata con lo stesso argomento venga restituito il valore direttamente invece di doverlo ricalcolare. Il problema ha tutto l'aspetto di essere uno di programmazione dinamica. Non mi è comunque del tutto chiaro il tuo procedimento (anche se non mi sembra tu possa fare ricorso alla memoizzazione da quello che ho capito nel tuo procedimento). Prova a scriverlo come pseudocodice e poi vediamo.