Problema dello zaino: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
m →‎Soluzione problema dello zaino senza limiti: il peso complessivo puo essere anche uguale al peso massimo consentito
Riga 72:
 
== Algoritmo Greedy ==
Martello e Toth (1990) proposerohanno utilizzato un'[[euristica]] [[Algoritmo greedy|greedy]] per risolvere il problema dello zaino. La loro versione ordina gli oggetti in ordinebase decrescenteal diloro pesocosto perunitario, inserirlivale nelloa zainodire fino<math>\frac{c_i}{w_i}</math> all'esaurimentoe delloli spazioesamina disponibilein ordine decrescente. Se ''k'L'oggetto ècorrente ilviene massimoinserito numerose die oggettisolo chese possonoil esseresuo inseritipeso nellonon zaino,supera l'algoritmola [[Algoritmocapacità greedy|greedy]]residua garantisce che ne siano inseriti nello zaino almeno <math>\frac{k}{2}</math>corrente.
 
Sono possibili molte variazioni di questo algoritmo, la più efficiente prevede di ordinare gli elementi in base al loro costo unitario, vale a dire <math>\frac{c_i}{w_i}</math> ed inserirli in ordine decrescente (euristica CUD).
 
È bene far notare come questi algoritmi siano euristici: essi, quindi, non garantiscono l'ottimalità della soluzione ma sono in grado di fornire una "buona" soluzione in tempo ragionevole; spesso questo tipo di algoritmi viene utilizzato in approcci di enumerazione implicita come gli algoritmi [[Branch and bound]].