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.
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 
)
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”.
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 (119,9 KB)
grazie mille, ora guardo.
Se lo scrivi in modo furbo e usi un unordered_set puoi risolverlo in tempo esponenziale 
Ci sono due modi per affrontare il knapsack, uno con complessità di memoria NW e l’altro con 2W.
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
2 Mi Piace
grazie mille, mi metto subito al lavoro
Come lo risolveresti con un unordered_set?
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
lowaltrimenti 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.
2 Mi Piace
Grazie mille, ora provo