Trovare la combinazione più simile in un insieme di numeri
Salve,
avrei un problema di tipo combinatorio da risolvere:
Dato un insieme casuale di 36 numeri interi positivi, devo trovare la combinazione di uno o più numeri che sommati tra loro sia più vicina ad un dato valore S.
esempio con 7 numeri:
insieme=(14, 8, 1, 4 , 9, 8, 32) S=6 in questo caso la soluzione sarebbe:(1+4)
Ovviamente la cosa più semplice che viene in mente è: provare tutte le combinazione e prendere la migliore.
Purtroppo nel mio caso ho ben 36 numeri nell'insieme e quindi bisognerebbe fare 2^36 tentativi che sono troppi anche per un computer veloce.
Se qualcuno sa darmi qualche consiglio o indicarmi che tipo di algoritmo (se esiste) possa risolvere tale problema in modo più rapido mi sarebbe molto utile.
grazie
avrei un problema di tipo combinatorio da risolvere:
Dato un insieme casuale di 36 numeri interi positivi, devo trovare la combinazione di uno o più numeri che sommati tra loro sia più vicina ad un dato valore S.
esempio con 7 numeri:
insieme=(14, 8, 1, 4 , 9, 8, 32) S=6 in questo caso la soluzione sarebbe:(1+4)
Ovviamente la cosa più semplice che viene in mente è: provare tutte le combinazione e prendere la migliore.
Purtroppo nel mio caso ho ben 36 numeri nell'insieme e quindi bisognerebbe fare 2^36 tentativi che sono troppi anche per un computer veloce.
Se qualcuno sa darmi qualche consiglio o indicarmi che tipo di algoritmo (se esiste) possa risolvere tale problema in modo più rapido mi sarebbe molto utile.
grazie
Risposte
Grazie per la risposta,
comunque avevo già dato un'occhiata al "subset sum problem" ed anche se in effetti riporta una situazione abbastanza similare, sotto alcuni aspetti è diversa perchè nel mio caso non devo solo trovare se esiste o no il sottoinsieme ma anche sapere quale è.
Altra differenza è che ho solo numeri positivi e che non devo trovare l'uguaglianza della somma, ma quale combinazione è la più vicina al valore voluto.
Quindi leggendo la spiegazione mi risulta difficile capire se è possibile ed eventualmente come poter variare gli algoritmi spiegati per adattarli al mio caso.
comunque avevo già dato un'occhiata al "subset sum problem" ed anche se in effetti riporta una situazione abbastanza similare, sotto alcuni aspetti è diversa perchè nel mio caso non devo solo trovare se esiste o no il sottoinsieme ma anche sapere quale è.
Altra differenza è che ho solo numeri positivi e che non devo trovare l'uguaglianza della somma, ma quale combinazione è la più vicina al valore voluto.
Quindi leggendo la spiegazione mi risulta difficile capire se è possibile ed eventualmente come poter variare gli algoritmi spiegati per adattarli al mio caso.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo