Problema dello zaino: differenze tra le versioni

È 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]].

 

Si dimostra che il rilasciamento continuo del problema dello zaino è equivalente all'euristica CUD quando si permettono valori in [0, 1] delle variabili <math>x_i</math> (in particolare una sola variabile avrà valore non binario). In questo modo euristica e rilasciamento possono essere risolti simultaneamente in maniera efficiente.