# Knapsack problems **URL:** \ **Category:** Algoritmi\ **Created:** [24 Luglio 2017, 9:33am UTC](https://forum.olinfo.it/t/knapsack-problems/4732 "2017-07-24T09:33:46Z")\ **Posts on this page:** 12\ **Page:** 1
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [24 Luglio 2017, 9:33am UTC](https://forum.olinfo.it/t/knapsack-problems/4732/1 "2017-07-24T09:33:46Z")
Salve a tutti, ho provato a risolvere “Pranzo della nonna” e ho ottenuto 60/100. Ho scoperto che per risolverlo bisogna utilizzare questa tecnica chiamata “Knapsack”, ho cercato qualche video su youtube ma non ho capito molto bene come funziona. Qualcuno può per favore spiegarmi questa tecnica o mandarmi qualche fonte in italiano. Grazie in anticipo. ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [24 Luglio 2017, 9:52am UTC](https://forum.olinfo.it/t/knapsack-problems/4732/2 "2017-07-24T09:52:20Z")
Ciao, la tecnica è la _programmazione dinamica_ (knapsack è il nome di un problema “classico” che si risolve con programmazione dinamica) Nella guida alle selezioni territoriali la tecnica è spiegata in italiano (consiglio di leggere prima il capitolo sulla ricorsione). Puoi trovare la guida cercando qui sul forum o su Google (sono da telefono 😅) ---
**Author:** ![dp\_1](https://forum.olinfo.it/user_avatar/forum.olinfo.it/dp_1/32/2635_2.png) [@dp\_1](https://forum.olinfo.it/u/dp_1)\ **Post date:** [24 Luglio 2017, 10:08am UTC](https://forum.olinfo.it/t/knapsack-problems/4732/3 "2017-07-24T10:08:57Z")
Trovi la guida alle territoriali [qui](http://www.imparando.net/sito/olimpiadi_di_informatica/guida_quinta_edizione.pdf) ---
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [24 Luglio 2017, 11:58am UTC](https://forum.olinfo.it/t/knapsack-problems/4732/4 "2017-07-24T11:58:50Z")
La programmazione dinamica la conosco già infatti ho risolto poldo, rescaling, sommelier, discesa e forse anche altri. il problema è che non riesco a risolvere “Pranzo della nonna”. ---
**Author:** ![wil93](https://forum.olinfo.it/user_avatar/forum.olinfo.it/wil93/32/2862_2.png) [@wil93](https://forum.olinfo.it/u/wil93)\ **Post date:** [24 Luglio 2017, 12:50pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/5 "2017-07-24T12:50:16Z")
Questo pdf contiene una guida alla DP che parte dal problema dello zaino (knapsack) quindi potrebbe essere d’aiuto. Le ultime sezioni, 5 e 6, trattano altro. [dinamica.pdf](https://forum.olinfo.it/uploads/default/original/1X/6078b43e78dd194879963374bd4ca8d226c25502.pdf) (119,9 KB) ---
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [24 Luglio 2017, 12:53pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/6 "2017-07-24T12:53:25Z")
grazie mille, ora guardo. ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [24 Luglio 2017, 6:38pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/7 "2017-07-24T18:38:12Z")
Se lo scrivi in modo furbo e usi un `unordered_set` puoi risolverlo in tempo esponenziale 😉 ---
**Author:** ![doublechar14](https://forum.olinfo.it/user_avatar/forum.olinfo.it/doublechar14/32/426_2.png) [@doublechar14](https://forum.olinfo.it/u/doublechar14)\ **Post date:** [24 Luglio 2017, 10:12pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/8 "2017-07-24T22:12:26Z")
Ci sono due modi per affrontare il knapsack, uno con complessità di memoria N_W e l’altro con 2_W. Io se ricordo bene sono riuscito a risolverlo con N\*W calcolandomi però quale potesse essere uno qualsiasi dei pesi possibili. Io sono riuscito a capirlo grazie a questo pdf: [http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf](http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf) ---
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [25 Luglio 2017, 1:45pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/9 "2017-07-25T13:45:54Z")
grazie mille, mi metto subito al lavoro ---
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [25 Luglio 2017, 5:29pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/10 "2017-07-25T17:29:00Z")
Come lo risolveresti con un unordered\_set? ---
**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\ **Post date:** [25 Luglio 2017, 6:16pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/11 "2017-07-25T18:16:56Z")
La soluzione esponenziale prevedere di provare tutte le possibili somme, quindi ti tieni un `unordered_set` con tutte le somme parziali e per ogni nuovo valore aggiungi tutte le possibili nuove somme. Si usa un `unordered_set` (potresti anche usare un `set` ma è più lento) perchè non contiene duplicati e quindi evito di fare somme inutili. Adesso si può vedere che il numero delle somme è esponenziale, tuttavia si osserva che K è relativamente piccolo ≤ 5000, quindi se per ogni valore P\_i≥K lo ignoro, il numero di somme parziali non supererà mai K. Adesso si può notare che la complessità di questo algoritmo è scesa da \mathcal O(2^N) a \mathcal O(N⋅K) che è sufficiente per risolvere il problema (io ho provato e ho ottenuto 0,824s che rientra a malapena). Quindi ricapitolando: - Inizializzo una variabile `low` (o come vuoi chiamarla) a 10^6 - Per ogni nuovo valore calcolo tutte le possibili somme con i valori precedenti e se sono maggiori di K aggiorno la variabile `low` altrimenti le aggiungo al set (fai attenzione a non aggiungere le nuove somme finché non le hai calcolate tutte altrimenti la sommi a se stessa) - La risposta al problema è -ovviamente- `low`. ---
**Author:** ![Luca25](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/82dd89/32.png) [@Luca25](https://forum.olinfo.it/u/Luca25)\ **Post date:** [25 Luglio 2017, 7:08pm UTC](https://forum.olinfo.it/t/knapsack-problems/4732/12 "2017-07-25T19:08:59Z")
Grazie mille, ora provo