Donné une somme cible et un ensemble d'entiers, trouver le plus proche sous-ensemble de nombres qu'ajouter à la cible

J'ai un ensemble d'entiers M et une somme cible k. Je veux trouver le sous-ensemble de M qui est la plus proche de k sans.

Par exemple:

M = {1, 3, 5, 5, 14}

k = 12

answer = {1, 5, 5}

because 1 + 5 + 5 = 11 and there is no way to make 12.

J'ai la contrainte supplémentaire que le sous-ensemble peut contenir au plus 4 éléments.

Dans mon application, la taille de |M| peut être de grande taille (de l'ordre de plusieurs milliers d'éléments). Si il n'est pas possible de trouver les paramètres optimaux de réponse dans un délai raisonnable, je suis intéressé par des solutions qui, au moins, donner une "bonne" réponse.

Maintenant je suis à la résolution de ce problème en générant de 10 000 sous-ensembles aléatoires et de la sélection la plus proche, celui qui fonctionne le mieux que l'on pourrait attendre mais est très lent. Je ne suis pas sûr de savoir comment loin d'être optimale, ce qui est réellement, mais aucune indication sur qui serait intéressant pour moi en tant que bien.

Et juste pour confirmer, vous voulez que le réel sous-ensemble, et pas seulement la somme?
Quelle est la taille de l'individu valeurs entières? Existe-il des négatifs d'entre eux?
Les entiers sont tous positifs. Ils s'étendent sur environ 7 ordres de grandeur (c'est à dire de 1 à 1M), mais la plupart sont [1...10000].
Oui, je suis à la recherche de la plus proche sous-ensemble avec le max de l'ordre de 4.

OriginalL'auteur John Shedletsky | 2013-10-24

  1. 11

    Puisque vous avez une limite sur le nombre d'éléments que vous pouvez choisir, vous pouvez le faire avec une assez simple algorithme.

    L'algorithme produit les éventuelles sommes dans "générations". Chaque élément d'une génération se compose d'un nombre représentant la somme, et d'un N-tuple de l'index dans M qui ont été utilisés pour construire cette somme.

    Génération zéro est vide; la production X+1 est produite par la marche de la génération X, et en ajoutant les éléments de M pour chaque valeur de cette génération, et l'enregistrement de leur somme pour la prochaine génération X+1.

    Avant le calcul de la somme, de vérifier son N-tuple de la présence de l'indice du nombre que vous êtes sur le point d'ajouter. S'il est là, sautez le nombre. Ensuite, vérifiez la somme: si il est déjà présent parmi les X+1 sommes, de l'ignorer; sinon, enregistrez la nouvelle somme, avec la nouvelle N-tuple d'index (ajouter l'indice du nombre que vous avez ajouté à la N-tuple de la génération X).

    Ici est de savoir comment cela pourrait fonctionner pour les entrées:

    De génération 0: vide

    Génération 1:

     1 - {0}
 3 - {1}
 5 - {2}
14 - {4}

    Génération 2:

     4 - {0, 1}
 6 - {0, 2}
 8 - {1, 2}
10 - {2, 3}
15 - {0, 4}
17 - {1, 4}
19 - {2, 4}

    Génération 3:

     9 - {0, 1, 2}
11 - {0, 2, 3}
13 - {1, 2, 3}
18 - {0, 1, 4}
20 - {0, 2, 4}
22 - {1, 2, 4}
24 - {2, 3, 4}

    Génération 4:

    14 - {0, 1, 2, 3}
23 - {0, 1, 2, 4}
25 - {0, 2, 3, 4}
27 - {1, 2, 3, 4}

    Vous pouvez maintenant effectuer une recherche par le biais de quatre générations pour un certain nombre qui est le plus proche de votre cible nombre k.

    C'est une manière intelligente de ré-utiliser le travail comme on le fait d'une recherche exhaustive. Merci pour l'idée.
    Cette "intelligence" est communément appelé de la programmation dynamique.
    Ce est O(n^4), dans le pire des cas, non? Si il n'y a pas de chevauchement des sommes, il y aura n^4 éléments dans la 4ème génération.
    Oui, afin de réaliser une accélération de l'algorithme nécessite des chevauchements. Si il n'y a pas de chevauchements, l'algorithme s'exécuter en O(n^4).
    Bon travail mentionnant la Génération X!

    OriginalL'auteur dasblinkenlight

  2. 2

    Si la cible somme k n'est pas trop grand, regardez http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution - vous pouvez l'utiliser pour créer une image bitmap qui vous indique les nombres qui peuvent être produites à l'aide de votre sous-ensemble. Ensuite, il suffit de choisir le plus proche possible du nombre de k dans le bitmap.

    Ne sera pas une approximation de l'algorithme plus de sens ici?
    Ce que j'ai décrit a une calculer facilement le coût de la plupart des Mk et si vous pouvez vous permettre cela - donne la bonne réponse. C'est à l'OP, qu'ils peuvent le justifier. Si vous voulez une approximation, tour de tous les nombres à un multiple de G pour quelques G puis divisez-le par G. Cela réduit le coût en réduisant efficacement k à k/G.

    OriginalL'auteur mcdowella

  3. 2

    Diviser le problème en 4 parties:

    • Somme, contenant exactement 1 élément

      Simplement parcourir et trouver la valeur la plus élevée ne dépasse pas la taille de la cible.

    • Somme, contenant exactement 2 éléments

      Utiliser une double boucle for pour trouver la somme la plus importante n'est pas plus large que la cible.

    • Somme, contenant exactement 3 éléments (similaire à 3SUM)

      Trier les éléments

      Utiliser une double boucle for et faire une recherche binaire pour la cible moins deux valeurs, à la recherche pour les petites valeurs de trouver la somme la plus importante n'est pas plus large que la cible.

    • Somme, contenant exactement 4 éléments

      Trier les éléments (déjà fait)

      Utiliser une double boucle for pour générer toutes les sommes de 2 éléments.

      Maintenant, pour chaque somme, faire une recherche binaire sur les sommes pour la cible, à la recherche de valeurs plus petites jusqu'à ce que nous en trouver un qui ne contiennent pas de soit la valeur de cette somme est composée de.

      Voir cette de code à l'aide de cette approche pour un problème similaire (la somme exacte).

    Moyen temps de marche (?) = O(n + n^2 + n^2 log n + n^2 log n) = O(n^2 log n).

    Déterminer le temps d'exécution de ce dernier problème est un peu difficile, il peut être aussi mauvais que O(n^4 log n) dans le pire des cas, comme vous pouvez vous retrouver à la recherche par le biais de la plupart d'entre eux avant d'en trouver un qui s'adapte, mais cela devrait se produire rarement, et, dans la même exécution, certains devraient prendre moins de temps, donc le temps de course total peut être moins.

    OriginalL'auteur Dukeling