Ho un problema che si riduce ad avere un insieme di interi e che vogliono il sottoinsieme di quei numeri interi la cui somma è più vicina ad alcuni target senza andare oltre. Qual è un buon algoritmo per fare questo? Forse è anche un problema noto il cui nome non lo so?
È il " Problema dello zaino " ed è abbastanza noto. Algoritmi efficienti sono difficili in quanto il problema è NP-Complete. Ciò significa che non è garantita una soluzione di tempo polinomiale per tutti i casi del problema sebbene esistano alcuni algoritmi per risolverlo. Lo fanno piuttosto lentamente.
Un esempio del tuo problema perché ho capito che hai numeri:
1,2,7,22,199,3,5,6,12
e vuoi un sottoinsieme tale che la somma dei numeri nel sottoinsieme selezionato sia maggiore di 17.
Un approccio semplice sarebbe quello di ordinare prima l'input per ottenere:
1,2,3,5,6,7,12,22,199
ora inizia ad aggiungere fino alla somma > 17
avresti aggiunto l'enterite 0,1,2,3,4,5,6 dell'array di cui sopra, quelle enteriti rappresentano sottoinsiemi che soddisfano i tuoi criteri. Tuttavia, per un insieme di input, la soluzione potrebbe non esistere affatto o potrebbero esserci molte soluzioni.
Leggi altre domande sui tag algorithms