정수 나누기

Question

아래에 설명 된 알고리즘 문제에 대한 해결 방법에 문제가 있습니다.

우리는 정수의 집합 (예 : 배열)을 가지고 있습니다. 우리의 임무는 합계가 서로 같다는 것을 그룹들로 나누는 것입니다 (그들은 같은 양의 요소를 가질 필요가 없습니다). 나는 원초적인 세트가 나눌 수없는 경우 우리는 "나누기 불가능한"대답을 주어야만한다.

예 : 집합 A은 [-7 3 3 1 2 5 14]입니다. 대답은 [-7 14], [3 3 1], [2 5]입니다.

확실히 불가능할 때 말할 수있는 것처럼 보입니다. 원시 집합의 합이 3 : sum(A) % 3 != 0으로 나눌 수없는 경우.

이 문제를 해결하는 방법에 대해 알고 계십니까?

Answer 1

이것은 partition problem의 변형이며, 기본 파티션 문제는 세트가 서로가 같은 두 세트 (세 개가 아님)로 분할된다는 점입니다. 이 문제는 NP로 완성되어 있으므로 다항식 시간 솔루션을 찾을 수 없을 것입니다. 2 파티션 문제는 의사 다항식 시간 솔루션을 갖지만 3 파티션 문제는 발생하지 않습니다.

2 파티션 알고리즘을 3 파티션 알고리즘에 적용하는 방법에 대한 개요는 this answer을 참조하십시오. 병렬 솔루션에 대해서는 this paper을 참조하십시오.