Comment trouver quels numéros dans un ensemble s'additionnent à un autre numéro donné?

Question

Il semble que je rencontre un problème avec un système de comptabilité.

J'ai un ensemble d'opérations, mais leur somme ne correspond pas au montant que le service de la comptabilité pense qu'il devrait. Ils ne remettent pas en cause les calculs, mais uniquement les transactions incluses: p

Existe-t-il un algorithme qui m'aiderait à déterminer quelles transactions de l'ensemble ne devraient pas être incluses pour que la somme corresponde à un montant donné.

Given Set:  
2  
4  
5  
7

Given Sum Amount:
13

Result Set:
2
4
7

Modifier: Il y a moins de 100 transactions dans l'ensemble. Quelqu'un a-t-il un exemple en C # puisqu'il n'en existe aucun sur le Résolution du problème NP-complete problème dans XKCD question?

J'aurais dû obtenir un diplôme de CS.

Answer 1

Il s’agit du problème Subset Sum , qui est NP-Complete . Mais cela ne signifie pas qu’il n’ya pas d’algorithme pour trouver une somme de sous-ensembles.

Answer 2

Il s'agit du problème de sac à dos et de son statut NP-Complete. Vous ne pourrez pas résoudre facilement ce problème avec autre chose que de petits ensembles d’entrée. Pour tout ensemble de problèmes de taille décente, il s’agit de l’un de ces problèmes de résolution de la vie.

Cela dit, il existe des solveurs de sac à dos utilisant un algorithme génétique.

Answer 3

Comme l'ont dit les membres ci-dessus, il s'agit du problème de la sous-somme (ou du problème du sac à dos). Cependant, dire que cela ne peut pas être fait efficacement n’est pas très précis. Cela peut être fait, mais pas en temps polynomial. La solution est en fait assez simple en utilisant la programmation dynamique et récursion (et en temps pseudo-polynomial).

Étant donné les entiers [a_1, ..., a_n] et un nombre T,

Définissez le tableau S [i, k] pour indiquer s’il existe un sous-ensemble d’éléments entre a_1, ... a_i qui totalisent k. (Ceci est une matrice binaire).

Nous pouvons ensuite définir une relation récursive comme suit:

S [i, k] = S [i-1, k] ou S [i-1, k-a_j]

En d'autres termes, cela signifie que nous utilisons l'élément a_i ou non. La réponse sera localisée à S [n, T].

Quelle est la charge de travail pour construire la matrice S? Eh bien, S a n * T éléments. Pour calculer chaque élément, nous devons faire O (1) travail. Donc, le fonctionnement complet le temps est O (n * T).

Maintenant, à ce stade, il semble que j’ai prouvé que P = NP, comme ceci semble être un algorithme de temps polynomial. Cependant, rappelez-vous que nous mesurons la taille d'entrée en binaire, donc T = 2 ^ p pour certains p.

Je ne pense pas que quiconque dirait que la solution ci-dessus, quand correctement mis en œuvre est déraisonnable. En fait, pour beaucoup taille de problème raisonnable, il fonctionnera admirablement.

De plus, il existe des heuristiques pour résoudre ce problème, mais je suis pas un expert dans ce domaine.

Answer 4

Ceci est une version du le problème de sac à dos . C'est complet NP, donc vous ne obtiendrez pas une bonne réponse générale. Quelle est la taille de vos ensembles de transactions? Est-ce 5 comme vous l'avez montré, ou est-ce plutôt 500?

Answer 5

OK Beaucoup de gens ont donné le nom du problème et ont mentionné à quel point il est difficile à résoudre. Et en général, ils sont corrects. Cependant, vous devez résoudre un cas très spécifique. La première question à poser est de savoir si vous pensez ou non que vos 100 transactions sont sur le point d'être les bonnes. Vous avez un total ("votre" total). Ils ont un total. ("réel" total). Certaines de vos transactions sont donc fausses. Si vous soupçonnez qu'il n'y a que quelques transactions fictives, ce n'est pas si grave. Par exemple, considérons le cas où il n’existe qu’une transaction fictive. Dans ce cas, il nous suffirait de vérifier 100 numéros différents. S'il y a 2 faux trans, alors vous envisagez 100 * 99 contrôles, et les choses vont devenir fous à 4 faux trans, avec presque 100 000 000 de pas. mais si tout ce que vous faites est d’ajouter des int qui ne sont pas trop terribles.

Un autre raccourci possible consiste à examiner la nature de vos données (est-il possible d'enregistrer les 100 "numéros" et la somme attendue?). Quelle est votre somme par rapport à la somme réelle? Y at-il des valeurs si grandes que les éliminer rendrait votre somme soudainement inférieure à la somme réelle? Si c'est le cas, vous savez que ces valeurs ne peuvent pas être fausses. Par exemple, dans votre exemple, 7 est absolument requis.

Answer 6

        bool bBreak = false;
        int iEnd = 13;
        ArrayList ar1 = new ArrayList();
        ar1.Add(2);
        ar1.Add(4);
        ar1.Add(5);
        ar1.Add(7);

        String s1 = " ";
        foreach (int i in ar1)
        {
            if (i == iEnd)
            {
                s1 = "Result = " + i;
                bBreak = true;
            }
            if (bBreak) break;
            ArrayList ar2 = new ArrayList();
            ar2.AddRange(ar1);
            ar2.Remove(i);
            foreach (int j in ar2)
            {
                if ((i + j) == iEnd)
                {
                    s1 = "Results = " + i + ", " + j;
                    bBreak = true;
                }

                if (bBreak) break;
                ArrayList ar3 = new ArrayList();
                ar3.AddRange(ar2);
                ar3.Remove(j);
                foreach (int k in ar3)
                {
                    if (bBreak) break;
                    if ((i + j + k) == iEnd)
                    {
                        s1 = "Results = " + i + ", " + j + ", " + k;
                        bBreak = true;
                    }
                }
            }
        }
        Console.WriteLine(s1);

Answer 7

Oui c'est possible. Pas sûr si ce poste est toujours ouvert. Mais vous voudriez faire le complément Excel Solver. Postez tous les nombres, avec 1 sur la cellule adjacente. Ensuite, mettez le numéro de sortie souhaité .. puis tous les nombres utilisés conserveront leur "1" adjacent, tandis que ceux qui ne le seront pas deviendront "0". Faites ensuite une formule de filtrage qui ne répertorie que ceux qui ont un "1". à côté de ça.