Найдите итоговые значения подмножества для огромного набора данных

Question

1-й из всех:Я не программист, никогда не изучал программирование / алгоритмы.На самом деле мне приходится программировать, в основном на awk или ruby, на каком-нибудь bash.

В сегодняшней задаче у меня есть огромный набор данных (числа с плавающей запятой) в обычном текстовом файле, одна запись / строка и сумма всех чисел набора, но сумма неправильная, потому что некоторые числа (может быть только одно) в наборе отрицательные, но мы не можем видеть это в файле (нет знака, если элемент отрицательный).

Но я должен найти это / их:итак, сначала я вычислил правильную общую сумму (с добавлением всех чисел с awk) не заботился об их знаках.Теперь я подсчитываю разницу между первоначальной суммой (которая заботилась о знаках) и моей новой общей суммой.Но я должен найти все подмножества набора данных, которые имеют точно такую же сумму, как разница / 2.

Например.:

DATA:
1,2,3,4,5

ORIG SUM: 
5  

Теперь мы можем вычислить разницу между 1+2+3+4+5 - ИСХОДНОЙ СУММОЙ:15-5=10.10/2 = 5, поэтому мне нужно найти все подмножества, которые могут составить до 5, то есть [1,4],[2,3],[5].

Есть ли правильный способ сделать это?Я предпочитаю awk, ruby, сценарии оболочки, но приемлемы как python, так и perl (без интенсивного использования внешних библиотек, поскольку у меня нет права их устанавливать).

Заранее благодарю.

Answer 1

Вы имеете в виду SUBSET SUM проблема, известная в информатике?

Подсказка:Посмотрите в связанных вопросах, там есть МНОГО вопросов / ответов по этой проблеме.