Quale algoritmo dovrei usare per trovare la soluzione più vicina a un dato totale utilizzando un elenco di numeri interi?

Question

Il mio problema è questo:

Diciamo che ho una lista arbitraria di numeri interi A [2013, 54, 3, 32 1, 23 ...]

Qual è la migliore strategia per trovare quale di quei numeri dovrei aggiungere insieme per avere una somma uguale o più vicina a un dato numero?

Ovviamente c'è sempre il metodo della forza bruta ma sono interessato a saperlo se c'è un più ottimizzato.

Answer 1

Quando imballa i bagagli in una macchina, si mettono in primo luogo gli articoli più grandi e poi si adattano agli oggetti più piccoli attorno a loro. Per analogia, un approccio euristico al tuo problema è iniziare con il membro del tuo set più grande possibile mentre è ancora più piccolo del tuo obiettivo. Quindi ripetere il processo per la differenza tra il tuo totale corrente e il tuo obiettivo, e così via. Questo è noto come un Algoritmo avido .

Ad esempio, se il set è $ \ {2,3,5,8,13,21, 34} $ e il tuo obiettivo è $ 32 $ , inizia con $ 21 $ (il valore più grande inferiore a $ 32 $ ), quindi aggiungere $ 8 $ (perché questo è il grande valore inferiore a $ 32-21= 11 $ < / span>), quindi aggiungere $ 3 $ .

Un algoritmo avido è veloce e semplice, ma non ti darà sempre la soluzione migliore. Ad esempio, se il tuo set è $ {1, 5, 23, 26 \} $ e il tuo obiettivo è $ 30 $ Quindi l'algoritmo avido dà $ 26 + 1= 27 $ , mentre la soluzione migliore è $ 23 + 5 + 1= 29 $ .

Answer 2

Il problema è completo, ma polinomiale nel valore del numero specificato, con un grado poligomiale piuttosto basso. È difficile solo se i numeri coinvolti sono grandi.

Ordinamento dal più piccolo al più grande e aggiungendo fino a quando non ci si adatta al numero non è molto intelligente, perché sarà probabilmente un numero piuttosto grande che non si adatta, e non si avvicini alla somma desiderata. Molto meglio per risolvere il più grande per il più piccolo e aggiungere prima i numeri più grandi.

Ora se hai oggetti con una somma chiudi a s, puoi provare a migliorare questo. Ad esempio se la tua somma è troppo piccola per 117, ma il più piccolo oggetto inutilizzato è 317, provare se hai un elemento X nella tua lista e un articolo y non nell'elenco, dove Y è di circa 200 più piccoli di x - Scambia X contro Y, aggiungi l'elemento di taglia 317. Anche un semplice algoritmo ti troverà probabilmente un buon miglioramento.

Un metodo completamente diverso: lasciare che la somma desiderata sia, con una S. molto grande (come molti trilioni). Poi puoi scegliere una S 'Say circa 1.000.000, moltiplicare tutti i numeri coinvolti da (s' / s), trova oggetti con una somma vicino a 1.000.000, quindi scegli gli elementi originali. Prova per alcune somme vicino a 1.000.000.

Answer 3

Grazie al commento di @yuval sono stato portato al problema dello zaino che è esattamente quello che stavo cercando.

Anche se non ho capito gran parte delle soluzioni proposte a questo problema completo-NP in Wikipedia, ho pensato a un approccio rapido ma totalmente inaffidabile:

Basta ordinare l'elenco di numeri interi disponibili dal più piccolo al più grande e iniziare ad aggiungerli fino a quando la condizione desiderata non è soddisfatta.

Penso che se tutte le differenze tra due membri del set di Integer non variano molto allora questo approccio probabilmente darà la soluzione migliore e solo.