Quel algorithme dois-je utiliser pour trouver la solution la plus proche à un total donné à l'aide d'une liste d'entiers?

Question

Mon problème est ceci:

Disons que j'ai une liste arbitraire d'entiers A [2013, 54, 3, 32 1, 23 ...]

Quelle est la meilleure stratégie pour trouver lequel de ces chiffres que je devrais ajouter ensemble pour avoir une somme égale ou la plus proche d'un nombre donné?

évidemment, il y a toujours la méthode de la force brute, mais je suis intéressé à savoir s'il y a un plus optimisé.

Answer 1

Lorsque vous emballez des bagages dans une voiture, vous mettez les plus gros articles d'abord, puis adaptez les éléments les plus petits autour d'eux. Par analogie, une approche heuristique de votre problème est de commencer avec le membre de votre ensemble aussi grand que possible tout en étant plus petit que votre cible. Répétez ensuite le processus pour la différence entre votre total actuel et votre cible, etc. Ceci est connu sous le nom de Algorithme gourmand .

Par exemple, si votre jeu est $ \ {2,3,5,8,13,21, 34 \} $ Et vous cible est $ 32 $ , commencez par 21 $ (la plus grande valeur inférieure à $ 32 $ $ ), ajoutez $ 8 $ (car il s'agit de la grande valeur inférieure à $ 32-21= 11 $ < / span>), ajoutez ensuite $ 3 $ .

Un algorithme gourmand est rapide et simple, mais ne vous donnera pas toujours la meilleure solution. Par exemple, si votre jeu est $ \ {1, 5, 23, 26 \} $ et que vous cible est $ 30 $ $ alors l'algorithme gourmand donne 26 $ + 1= 27 $ , tandis que la meilleure solution est $ 23 + 5 + 1= 29 $ .

Answer 2

Le problème est NP-complet, mais polynôme dans la valeur du nombre donné, avec un degré de polynôme assez bas. Ce n'est que difficile si les chiffres impliqués sont grands.

Tri des plus petits à la plus grand et en ajoutant jusqu'à ce que aucun nombre ne fonctionne pas très intelligent, car il s'agira probablement d'un nombre assez important qui ne convient pas, et vous ne serez pas proche de la somme souhaitée. Beaucoup mieux pour trier du plus grand au plus petit et ajoutez d'abord les plus gros chiffres.

Maintenant, si vous avez des articles avec une somme ferme à s, vous pouvez essayer d'améliorer cela. Par exemple, si votre somme est trop petite d'ici 117, mais le plus petit élément inutilisé est 317, vous allez essayer si vous avez un élément X dans votre liste, et un élément Y pas dans la liste, où y est d'environ 200 plus petit que X - Swap x contre Y, ajoutez l'élément de taille 317. Même un simple algorithme trouvera probablement de bonnes améliorations.

Une méthode complètement différente: laissez la somme souhaitée être s, avec un très grand S (comme beaucoup de billions). Ensuite, vous pouvez choisir un SO »d'environ 1 000 000, multiplier tous les numéros impliqués par (S '/ S), trouver des éléments avec une somme proche de 1 000 000, puis choisissez les éléments d'origine. Essayez quelques sommes proches de 1 000 000.

Answer 3

Grâce au commentaire de @yuval, j'ai été conduit au problème du sac à dos qui est exactement ce que je cherchais.

Bien que je n'ai pas compris une grande partie des solutions proposées à ce problème complet de Wikipedia, j'ai pensé à une approche rapide mais totalement peu fiable:

Trier simplement la liste des entiers disponibles de la plus petite au plus grand et commencez à les ajouter jusqu'à ce que la condition souhaitée soit remplie.

Je pense que si toutes les différences entre deux membres de l'ensemble d'entier ne varient pas beaucoup, cette approche va probablement donner la meilleure solution.