X까지 합계 된 배열 Z의 가능한 모든 하위 배열 찾기

Question

비교적 복잡한 문제가 있습니다. 주어진 배열에 대해 X까지 합계 된 배열에서 가능한 모든 하위 배열을 찾는 알고리즘이 필요합니다.

{2,8,12,45,32,7,6,5} 

우리가 서브 어레이 (20)에 그 금액을 필요하다고 할 수 있습니다, 일부는 다음과 같습니다

{7,7,6} {5,5,5,5} {8,8,2,2} 

:

는

{8,12} {2,7,6,5} {12,6,2} 

그러나 같은 조합이있을 것3210

가능한 모든 금액이 필요합니다.

나는 모든 가능성을 무차별 체킹하고있는 솔루션을 만들었지 만 (너무 길어서 (어떤 경우에는 30 분을 초과하는 경우도 있음) 완료해야하기 때문에 머리를 부딪히는 똑똑한 해결책이 필요하다. 이제 며칠 동안 끝났어.

Answer 1

귀하의 질문은 반복되는 대답이 용인 할 수 있으며, summands를 주문할 수있는 모든 가능한 방법을 생성하고 싶지는 않은 것으로 보입니다. 나는 그것에 대한 나의 답을 기본으로 삼을 것이다.

저는 이것을 C++로 구현할 것입니다. 데이터 구조로서, 나는 아마 이런 식으로 뭔가를 사용하십시오 :

struct partial_sum { 
    int min_last_summand; 
    std::vector< std::pair<partial_sum*, int> > prefixes; 
}; 

std::map<int, partial_sum*> m; 

여기에 중앙 조각은지도 m입니다. 그것은 합계의 값을 얻는 방법에 대한 정보에 맵핑합니다. NULL에 매핑 된 0으로 초기화 할 수 있습니다. prefixes 회원은 주어진 합계를 얻는 모든 가능한 방법에 대한 데이터를 저장합니다. 각 쌍의 첫 번째 부분은 마지막 제외한 나머지 모든 summand에 대한 정보에 대한 포인터를 제공합니다. 두 번째 부분은 마지막 구성원을 제공합니다. 이는 합계가 많은 합계의 접두어가 될 수 있고 합계에는 여러 가지 접두사가있을 수 있지만 모든 접두사 합계의 값은 현재 합계의 값보다 작기 때문에 방향이 지정된 비순환 적 그래프 형식을 제공합니다.

중앙 반복 단계는 m에서 최소 엘크먼트를 제거하고 입력 세트의 요소를 방금 제거한 값에 추가 할 수있는 모든 가능한 방법을 생성합니다. 따라서 새로운 합계에 대한 새 항목을 삽입해야하는지 여부를지도에서 확인할 수 있습니다. 그리고 기존 항목과 새 항목 모두에 대해 prefixes 목록에 새 항목을 작성합니다. 방금 전에지도에서 제거한 포인터가 첫 번째 부분으로 추가되고 마지막으로 추가 한 summand가 두 번째 항목으로 추가됩니다.

모든 순열 생성을 피하기 위해 summands의 오름차순 (또는 오히려 내림차순) 순서로만 합계를 생성합니다. 일을 더 쉽게하려면이 min_last_summand 정보를 유지해야합니다. prefixes 목록에있는 쌍의 모든 두 번째 요소가 항상 포함되어야합니다. 새로운 합계를 생성 할 때 마지막 피연산자가 접두사의 최소 마지막 피연산자보다 작은 피연산자를 건너 뛸 수 있습니다. 이는 피연산자가 이전 피연산자보다 작음을 의미합니다. 또한 합계 값이 목표 합계보다 큰 경우 합계를 생성하지 않아도됩니다.

결과를 인쇄 할 때 대상 합계에서 도달 할 수있는 DAG 부분을 반복하고 거기에서 모든 경로를 루트 NULL까지 나열해야합니다. 따라서 각 재귀 단계에서 현재 부분 합계를 가리키는 포인터를 갖게됩니다. 해당 포인터가 NULL이면 0 개의 summands로 구성된 합계를 내 보냅니다. 그렇지 않으면 모든 prefixes을 반복합니다. 각 접두사에 대해 접두어를 쓸 수있는 모든 방법을 생성하지만 첫 번째 요소의 min_last_summand이 현재 마지막 summand보다 크지 않고 두 번째 요소가 따라 오는 summand보다 크지 않은 경우에만 반복됩니다 그것.즉, 다음 summand를 재귀 호출의 인수로 전달해야 함을 의미합니다. 함께 사용하면 내림차순으로 합계를 생성하지 않아도됩니다.

위의 접근 방식은 프로그램이 한 번 실행 된 후에 종료되므로 메모리를 확보하는 것에 대해 걱정할 필요가 없다고 가정합니다. 그렇게 할 경우, 작성한 모든 오브젝트에 대한 포인터를 저장해야하므로, 모든 오브젝트를 비울 수 있습니다.