합계를 계산하는 부분합을 찾는 방법은 무엇입니까?

Question

나는 특정 전체 구성 목록에서 번호를 찾을 필요가

:

Sum: 500 

Subtotals: 10 490 20 5 5 

In the end I need: {10 490, 490 5 5} 

어떻게 이러한 유형의 문제를 부르지을? 효율적으로 해결하는 알고리즘이 있습니까?

Answer 1

이것은 Knapsack problem이며 NP 완전 문제입니다. 즉, 알려진 효율적인 알고리즘이 없습니다.

Answer 2

1. 이것은 이 아니라 배낭 문제입니다.
2. 최악의 경우 N 개의 부분합을 사용하면 O (2^N) 개의 해가있을 수 있으므로 최악의 경우 모든 알고리즘이 이보다 더 좋지 않습니다 (따라서 NP 클래스에 전혀 속하지 않습니다)).

소계 배열에 양수가 아닌 요소가없고 모든 요소가 Sum보다 크지 않다고 가정 해 봅시다. 부분합의 배열을 정렬 한 다음 꼬리 합을 배열하여 끝에 0을 더할 수 있습니다. (
E : 어떤 "나머지 금액"S, 위치 내가, 그리고 "현재 목록"L 우리가 가진 문제 E (S, I, L) 지금

Subtotals: (490, 20, 10, 5, 5) 
PartialSums: (530, 40, 20, 10, 5, 0) 

: 당신의 예에서는 모양을 0, i, L) = (인쇄 L).
E (S, i, L) | (PartialSums [i] < S) = (아무것도 없음). (S, i + 1, L), E (S-Sumtotals [i], j, L | Subtotals [i]), 여기서 j는의 첫 번째 요소의 인덱스이다. 소계는 (S-Subtotals [i]) 또는 i + 1 중 큰 것보다 작거나 같습니다.
문제는 E (합계, 0, {})입니다.

물론 중복에 문제가 있습니다 (목록에 다른 490 숫자가있는 경우이 알고리즘은 4 가지 솔루션을 출력합니다). 그것이 당신이 필요로하지 않는 경우, 쌍 (값, 다중성)의 배열을 사용하는 것이 도움이 될 수 있습니다.

P. 문제의 크기가 충분히 작은 경우 동적 프로그래밍을 고려할 수도 있습니다.

1. {0}으로 시작하십시오. 소계 배열과 동일한 배열을 크기로 만듭니다.
2. 모든 부분합에 대해 부분합 값을 추가하여 이전 집합의 새 집합을 만듭니다. 합계보다 큰 모든 요소를 ​​제거하십시오. 이전 세트와 병합하십시오 (모든 가능한 합계의 세트가 될 것입니다).

3. 최종 세트에 합이 없으면 해결 방법이 없습니다. 그렇지 않으면 Sum에서 이전 솔루션에 [value] 및 [value-subtotal]이 포함되어 있는지 확인하면서 Sum에서 솔루션을 역 추적합니다.
   예 :

   (10, 490, 20, 5, 5)

세트 : 마지막 세트

(0) 
(0, 10) 
(0, 10, 490, 500) 
(0, 10, 20, 30, 490, 500) (510, 520 - discarded) 
(0, 5, 10, 15, 20, 25, 30, 35, 490, 495, 500) 
(0, 5, 10, 15, 20, 25, 30, 35, 40, 490, 495, 500) 

: 500-5] 이전의 세트에서, [495 -5], [490-20]은 이전 집합이 아니고 [490-490]은 0이며 결과는 {5, 5, 490}입니다.