대용량 데이터 세트의 하위 집합 합계를 찾으십시오.

Question

우선 순위 : 저는 프로그래머가 아니며 프로그래밍/알고리즘을 배웠지 않습니다. 사실 awk, ruby ​​또는 bash를 주로 프로그래밍해야합니다.

오늘 작업에서는 평범한 텍스트 파일, 레코드/라인 및 세트의 모든 숫자의 합계에 거대한 데이터 세트 (부동 소수점 숫자)가 있지만 합계는 잘못되었습니다. 일부 숫자 (단 하나 일 수 있음)는 음수이지만 파일에서이를 볼 수 없습니다 (요소가 음수이면 부호가 없습니다).

하지만 나는 그것들을 찾아야 만한다 : 그래서 처음에는 정확한 합계 (모든 숫자를 awk와 함께 추가 함)가 그들의 표지판을 신경 쓰지 않았다. 이제는 원래 합계 (기호에주의)와 새 합계의 차이가 있습니다. 그러나 차이점/2와 정확히 같은 합계를 가진 데이터 집합의 모든 하위 집합을 찾아야합니다.

예컨대 :

DATA: 
1,2,3,4,5 

ORIG SUM: 
5 

이제 우리는 1 개 + 2 + 3 + 4 + 5 차이 계산할 수 - 오리지널 SUM : 15-5 = 10. 10/2 = 5이므로 5, 즉 [1,4], [2,3], [5]까지 추가 할 수있는 모든 하위 집합을 찾아야합니다.

적절한 방법이 있습니까? 나는 awk, ruby, shell scripting을 선호하지만 Python과 Perl 모두 허용 가능하다. (외부 라이브러리를 많이 사용하지 않고도 설치할 수있다.)

미리 감사드립니다.

Answer 1

컴퓨터 과학에서 알려진대로 SUBSET SUM 문제가 있습니까?

힌트 : 관련 질문을 살펴보면 해당 문제에 대한 많은 질문/답변이 있습니다.