3

04102016: Sempre affascinato dal problema dello zaino o knapsack

161004_486px-knapsack-svgPassano gli anni e sono ancora affascinato dal problema dello zaino o knapsack.

.

Ai tempi dovevo riuscire a mettere sui due lati di una cassetta un album musicale.
Avevo questo problema: L’album che volevo copiare durava magari 78 minuti su CD, compravo una cassetta da 80, ma non era detto che se c’erano 10 canzoni, le due 5 per lato duravano spaccate 40 minuti

Con il tempo ho scoperto che questo era il problema del ladro, noto anche come problema dello zaino, detto anche Knapsack problem.
E’ un problema di ottimizzazione combinatoria posto nel modo seguente:
sia dato uno zaino che possa sopportare un determinato peso. Siano dati inoltre N oggetti, ognuno dei quali caratterizzato da un peso e un valore. Il problema si propone di scegliere quali di questi oggetti mettere nello zaino per ottenere il maggiore valore senza eccedere il peso sostenibile dallo zaino stesso.

Molti matematici ci hanno ragionato su, e esiste una pagina di wikipedia apposita, io avevo risolto con un programmino in Pascal:
– Compilavo con la durata delle canzoni mettendole semplicemente in ordine
– Cercavo di entrare nella fatidica durata dei 40 minuti per lato con le prime canzoni dell’album.
– Se non ci rientravo toglievo la più grande del lato A e cercavo la più piccola del lato B, scambiandole. Se ancora non ci rientravo ripetevo questa ultima operazione con le canzoni nel nuovo ordine rimaste.

Sicuramente non era un metodo ottimizzato, ma con le canzoni funzionava ^__^

(Visited 16 times, 1 visits today)

Leave a Reply

Your email address will not be published.


*


5