Problema dello zaino

[ilop]

Salve a tutti!
Qualcuno per caso ha la solozione con programmazione greedy del Problema dello Zaino nella sua versione generale, cioè dove è permesso inserire nello zaino anche frazioni di oggetti?
Grazie!

[Gica78R]

Originariamente inviato da ilop

Salve a tutti!
Qualcuno per caso ha la solozione con programmazione greedy del Problema dello Zaino nella sua versione generale, cioè dove è permesso inserire nello zaino anche frazioni di oggetti?
Grazie!

E' la prima volta che sento parlare di programmazione greedy...
Se puo' esserti utile, ho trovato questi due link:

http://www.disi.unige.it/person/MoggiE/ASD/nota9

http://web.tiscali.it/vitaartificiale/knap.html

Il "Problema dello zaino" credo sia un problema di ottimizzazione, vero? Mi sa che l'ho fatto nel corso di Ricerca Operativa, tanti tanti anni fa (ma per noi era il "Problema della sporta" ).

Ciao

[cionci]

Un algoritmo greedy cerca di ottimizzare la funzione facendo scelte ad ogni momento più convenienti rispetto alle altre...

Ad esempio se un algoritmo greedy dovesse percorrere un grafo, ad ogni nodo con più di un percorso sceglierebbe quello di costo minore...

[cionci]

In pratica un algoritmo grredy ad ogni passo deve sempre effettuare una scelta che determina (se possibile), fra tutte le scelte possibili, quella che permette di ottenere il valore maggiore della funzione da massimizzare...

Hai M oggetti...
Al passo i-esimo hai messo k oggetti nello zaino...
Per arrivare al passo i+1 un algoritmo greedy sceglierà l'oggetto degli M-k rimasti che permette di ottenere il valore più alto della funzione da massimizzare...

[Gica78R]

Originariamente inviato da cionci

In pratica un algoritmo grredy ad ogni passo deve sempre effettuare una scelta che determina (se possibile), fra tutte le scelte possibili, quella che permette di ottenere il valore maggiore della funzione da massimizzare...

Hai M oggetti...
Al passo i-esimo hai messo k oggetti nello zaino...
Per arrivare al passo i+1 un algoritmo greedy sceglierà l'oggetto degli M-k rimasti che permette di ottenere il valore più alto della funzione da massimizzare...

Non c'entra nulla con il backtracking?
Se ad ogni passo fai la scelta che ti massimizza la funzione, non e' detto che si giunga sempre ad una soluzione ammissibile, no? Quindi l'algoritmo deve valutare una situazione del genere e poter tornare indietro per effettuare una scelta differente.
O sono completamente fuori strada?

[cdimauro]

Il backtracking è un'altra cosa. Gli algoritmi che usano un approccio greedy funzionano esattamente come ha descritto cionci.

Nessuno, però, t'impedisce di usare entrambi gli approcci per cercare di risolvere un determinato problema...

[cionci]

Originariamente inviato da Gica78R

Non c'entra nulla con il backtracking?
Se ad ogni passo fai la scelta che ti massimizza la funzione, non e' detto che si giunga sempre ad una soluzione ammissibile, no? Quindi l'algoritmo deve valutare una situazione del genere e poter tornare indietro per effettuare una scelta differente.
O sono completamente fuori strada?

La soluzione che raggiungi è sempre ammissibile, ma non sai se è massima o meno...
Puoi anche applicare il backtracking anche ad un algoritmo greedy...ma cmunque per sapere se hai veramente il massimo dovresti ottenere tute le possibili soluzioni...

Supongo che con gli algoritmi genetici sarebbe carino da realizzare...

[Fuzzo]

Si, l'esame è quello di ricerca operativa
La soluzione del problema "rilassato" (frazioni) è questa:

• Ordini gli oggetti per utilità/peso decrescenti
• Effettui la scelta golosa, ovvero prendi dalla lista ordinata quanti più oggetti possibile fino a raggiungere il peso massimo
• Imposti un flag a true se la soluzione è ammissibile, ovvero se non carichi oggetti frazionati
• La soluzione con il flag a true e somma delle utilità maggiore è quella ottima (potrebbero essere più di una...)