Trouver des totaux de sous-ensembles pour un énorme ensemble de données

Question

Tout d'abord: je ne suis pas un programmeur, je n'ai jamais appris de programmation/d'algorithmes. En fait, je dois programmer, la plupart du temps en awk, ou ruby, un peu de bash.

Dans la tâche d'aujourd'hui, j'ai un énorme ensemble de données (nombres flottants) dans un fichier texte, un enregistrement/ligne et une somme de tous les nombres de l'ensemble, mais la somme est fausse, parce que certains des nombres (peut être seulement un) dans l'ensemble est négatif, mais nous ne pouvons pas le voir dans le fichier (il n'y a pas de signe si un élément est négatif).

Mais je dois le/la trouver: donc d'abord j'avais calculé la somme totale correcte (en ajoutant tous les nombres avec awk) ne se souciait pas de leurs signes. Maintenant, je maintenant la différence entre la somme originale (qui se souciait des signes) et ma nouvelle somme totale. Mais je dois trouver tous les sous-ensembles de l'ensemble de données, qui a exactement la même somme que la différence/2.

par exemple .:

DATA: 
1,2,3,4,5 

ORIG SUM: 
5 

Maintenant, nous pouvons calculer la différence entre 1 + 2 + 3 + 4 + 5 - ORIG SUM: 15-5 = 10. 10/2 = 5, donc j'ai besoin de trouver tous les sous-ensembles qui peuvent ajouter jusqu'à 5, c'est-à-dire [1,4], [2,3], [5].

Existe-t-il un moyen approprié de le faire? Je préfère awk, ruby, shell scripting, mais python et perl sont tous les deux acceptables (sans trop utiliser les bibliothèques externes, car je n'ai pas le droit de les installer).

Merci d'avance.

Answer 1

Vous voulez dire le problème SUBSET SUM connu en informatique?

Indice: Regardez dans les questions connexes, il y a BEAUCOUP de questions/réponses sur ce problème.