Discussione:Problema dello zaino

«Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo greedy garantisce che ne siano inseriti nello zaino almeno \frac{k}{2}.»

Siamo sicuri che sia corretto? se ho uno zaino di capacità C e ho n oggetti di peso C come faccio a metterne n/2? oppure è da intendersi che non ce ne potrebbero entrare mai piu' di uno? Ma anche qui, prendo 1 oggetto di capacita' C e n-1 di capacita' 1, l'algoritmo mettera' quello di capacita' C e non potra' mai mettere gli altri. giac.omo 19:50, 3 lug 2006 (CEST)

Penso che voglia dire che se, teoricamente, nello zaino ci stanno k oggetti, con questo algoritmo siamo sicuri di mettercene almeno k/2. --zar-(dimmi) 22:34, 3 lug 2006 (CEST)

intendi in una soluzione ottima ci stanno k oggetti? Se e' questo tanto vale scriverlo cosi'. giac.omo 09:15, 4 lug 2006 (CEST)

Credo di sì, anche la versione inglese non è tanto chiara. Questa è la mia interpretazione: se dopo aver provato tutte le combinazioni vediamo che al massimo lo zaino può contenere k oggetti, con l'algoritmo greedy (che non esplora tutto l'albero delle combinazioni) siamo però sicuri di metterne almeno k/2. --zar-(dimmi) 14:17, 4 lug 2006 (CEST)

In aggiunta all'attuale didascalia dell'immagine:

«In questo caso, la soluzione è di mettere nello zaino tre scatole gialle e tre grigie»

suggerirei di specificare che la soluzione indicata è valida per il problema dello zaino senza limiti. --Mommi84 (msg) 15:19, 2 nov 2009 (CET)

Ho sostituito " supportare " con " sopportare " un certo peso

Greedy

"Se k è il massimo numero di oggetti che possono essere inseriti nello zaino, l'algoritmo greedy garantisce che ne siano inseriti nello zaino almeno k/2." Questa affermazione e' sbagliata. In un algoritmo greedy che ordina in modo decrescente per peso, si potrebbe avere un caso del genere:

zaino capacita': 15

oggetti: {A: peso=14,valore=1}, {B: peso=1,valore=1}

soluzione greedy: 1 oggetto A

soluzione ottima: 15 oggetti B

Come potete vedere non c'e' alcuna garanzia di k/2 oggetti inseriti, e in generale un'euristica del genere non da alcuna garanzia. La pagina inglese invece, parla solo dell'algoritmo CUD (giustamente direi, in quanto quello che ordina solo per peso e' inutile), e questo ha la garanzia di inserire almeno il valore m/2 (m = valore ottimo inseribile). Se non ci sono obiezioni, riscrivero' il paragrafo. Wolf7 (msg) 14:27, 5 ago 2011 (CEST)

Corretto errore nella soluzione del 0-1 e resa omogenea la notazione

La funzione A(i,j) era definita erroneamente come "il massimo valore che può essere ottenuto con un peso minore o uguale a $j$ utilizzando fino a $i$ oggetti". Non è "utilizzando fino a i oggetti" ma "utilizzando i primi i oggetti". Mi sono permesso di riscrivere parte del paragrafo in maniera, spero, più chiara.

Per il resto, ho reso omogenea la notazione sui pesi e i valori che era disallineata col resto della voce: i pesi (chiamati "costi") erano indicati con c_i ed i valori con v_i.

Spero di essere stato utile. Saluti.