Voici un problème que je semble rencontrer de travailler avec un système comptable.
J'ai un ensemble de transactions, mais leur somme ne correspond pas au montant que le service comptable pense qu'il devrait. Ils ne questionnent pas les mathématiques, juste les transactions étant incluses: p
existe-t-il un algorithme qui m'aiderait à déterminer quelles transactions dans l'ensemble ne doivent pas être incluses pour que la somme correspondenne à un montant donné. EDIT:
Il y a moins de 100 transactions dans l'ensemble. Est-ce que quelqu'un a un exemple C # comme il n'y en a pas un sur le résolution du NP-complet problème dans XKCD question? l'homme, j'aurais dû recevoir un diplôme CS.
7 Réponses :
Ceci est le Problème de Knapsack et c'est NP-complet. Vous ne le résolvez pas facilement exactement avec quoi que ce soit, sauf des petits ensembles d'entrée. Pour tout problème de problème de taille décent, c'est l'une de ces problèmes de vie-de-Universe à résoudre.
Cela dit, il y a des solveurs de sacs à dos de gène-algorithme de génétique.
Ceci est une version de Le problème du sac à dos . C'est NP complète, alors vous n'allez pas avoir une bonne réponse générale. Quelle est la taille de vos ensembles de transactions? Est-ce que vous avez montré, ou est-ce plus comme 500?
Ceci est le Sous-ensemble Sum Problème, qui est np-complète . Mais cela ne signifie pas qu'il n'y a pas d'algorithme pour trouver un sous-ensemble somme.
+1 pour fournir une réponse plus précise que tout le monde. Le problème du sous-ensemble est un cas particulier du problème du sac à dos.
Mais ce est le problème du sac à dos. Il ne veut pas seulement demander si le sous-ensemble existe ou non, mais exactement ce que ce sous-ensemble est.
Ma compréhension est que la somme sous-ensemble est une correspondance exacte, tandis que le bon de sacs à dos plus généralisé trouve un montant maximum.
Comme les membres ci-dessus ont dit, il s'agit du problème de somme sous-ensemble (ou de problème de sacs à dos). Cependant, dire que cela ne peut pas être fait efficacement n'est pas très précis. Cela peut être fait, tout simplement pas en temps polynomial. La solution est en fait assez simple à l'aide de la programmation dynamique et la récursion (et dans le temps pseudo-polynomial).
donné des entiers donnés [a_1, ..., a_n] et un nombre t,
Définir le tableau S [I, K] pour noter s'il y a un sous-ensemble d'éléments entre a_1, ... a_i qui ajoutent jusqu'à 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 mots, cela signifie que nous utilisons l'élément A_i ou nous ne le faisons pas. La réponse sera située à S [N, T].
Quelle est la charge de travail pour construire matrix S? Eh bien, s a n * t éléments. Calculer chaque élément, Nous devons faire O (1) travail. Donc la course complète le temps est O (n * t).
Maintenant à ce stade, il semble que j'ai prouvé p = np, comme ça 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 mis en œuvre correctement est déraisonnable. En fait, pour beaucoup Tailles de problèmes raisonnables, il effectuera admirablement.
En outre, il existe des heuristiques pour résoudre ce problème, mais je suis pas un expert dans cette zone.
OK. Beaucoup de gens ont donné le nom du problème et ont mentionné comment le NP est difficile. Et en général, ils sont corrects. Cependant, vous avez un cas très spécifique dont vous avez besoin pour résoudre. La première question à demander est de savoir si vous pensez ou non que vos 100 transactions sont proches d'être les bonnes. Vous avez un total («votre» total). Ils ont du total. ("vrai" total). Certaines de vos transactions sont donc faux. Si vous soupçonnez qu'il n'y a que quelques bygus transactions là-bas, ce n'est pas si grave. Par exemple, considérons le cas où il n'y a qu'une seule transaction. Dans ce cas, nous devrions seulement vérifier 100 numéros différents. S'il y a 2 faux trans, alors vous envisagez des chèques de 100 * 99, et les choses deviendront folles à 4 bogus trans, avec près de 100 000 000 pas. Bien que si tout ce que vous faisiez, c'est ajouter des INT qui n'est pas trop terrible.
Un autre raccourci possible est d'examiner la nature de vos données (incidemment, est-il possible de poster les 100 "chiffres" et de la somme attendue?). Combien coûte votre somme sur la vraie somme? Y a-t-il des valeurs si grandes qui les élimineraient de rendre votre somme soudainement inférieure à la somme réelle? Si oui, vous savez que ces valeurs ne peuvent pas être les faux. Par exemple, dans votre exemple, 7 est absolument nécessaire.
Merci. Je pensais que sur la façon de réduire le sous-ensemble sur le trajet à la maison hier. Par exemple, l'ensemble de fonctionnement peut être réduit à un ensemble de transactions inférieures à la différence entre le total défini d'origine et le total attendu. Trouvez ensuite les transactions dans l'ensemble réduit dont la somme correspond à cette différence.
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);
Oui c'est possible. Je ne sais pas si ce post est toujours ouvert. Mais vous voudriez faire le complément Excel Solver. Postez tous les numéros, avec 1S sur la cellule adjacente. Ensuite, mettez le numéro de sortie souhaité .. Ensuite, tous les numéros utilisés, conserveront leur "1" adjacent, tandis que les personnes inutilisées vont se tourner vers "0". Ensuite, effectuez une formule de filtre qui ne répertorie que celles qui ont un "1" à côté de celui-ci.
La même question a été posée à un serveur ici: xkcd.com/287 avec un tas de solutions potentielles ici : Stackoverflow.com/questions/ 141779 / ...
Comme d'autres l'ont dit, cela ne peut pas être fait. Toutefois, si vous pouvez trouver un moyen de réduire l'espace de recherche en fonction des choses spécifiques à vos données, vous pourrez peut-être faire mieux. Mais aucun d'entre nous n'a suffisamment d'informations pour aider avec ceci ... et cela ne nous est probablement pas facilement fourni, même en supposant que vous soyez autorisé à le faire.
Brian, je ne pense pas que quiconque ait dit qu'il ne pouvait pas être fait, juste que ce serait difficile (mais je pense que je sais ce que vous vouliez dire).
@erich il n'est pas difficile de trouver un algorithme qui trouvera une réponse. Il peut juste prendre une longue période de longue durée. On pourrait presque dire que la solution est triviale à mettre en œuvre.
@tim: Je voulais dire "dur" comme un peu un jeu de mots dans la difficulté de trouver un algorithme, mais en trouvant la solution. NPC - NP-Hard - Vous obtenez ma dérive.