두 부분의 평균이 같도록 배열을 두 부분으로 나누는 방법은 무엇입니까?

배열을 두 부분으로 나누어 두 부분의 평균이 같도록하려면 어떻게합니까? 각 파티션에는 배열에서 인접하지 않은 요소가 포함될 수 있습니다. 제가 생각할 수있는 유일한 알고리즘은 기하 급수적입니다. 더 잘 할 수 있을까요?두 부분의 평균이 같도록 배열을 두 부분으로 나누는 방법은 무엇입니까?

출처

2012-01-18 CommonMan

솔직히 말해서 숙제 문제입니까? –

무엇을 시도 했습니까? 작동 했나요? 예제 입출력 예제가 있습니까? –

이것은 인터뷰 질문처럼 쉽게 들리지는 않습니다. – BrokenGlass

이 문제를 sum-subset problem (cached here)으로 줄일 수 있습니다. 여기에 아이디어가 있습니다.

A을 배열로 지정하십시오. S = A[0] + ... + A[N-1]을 계산하십시오. 여기서 N은 A입니다. k은 1에서 N-1까지이며, T_k = S * k/N이라고합시다. T_k이 정수인 경우 A의 하위 집합이 k이고 그 합은 T_k입니다. 당신이 이것을 할 수 있다면, 당신은 끝났습니다. k에 대해이 작업을 수행 할 수 없으면 그러한 파티션이 없습니다.

다음은이 접근 방식의 배경입니다. A의 파티셔닝이 있는데 두 부분의 평균이 같다고 가정하면 의 X과 y의 Y은 파티션입니다 (여기서 x+y = N). 그런 다음

sum(X)/x = sum(Y)/y = (sum(A)-sum(X))/(N-x)

이 있어야합니다 배열 정수를 포함하기 때문에 그렇게 대수의 약간 왼쪽은 정수,

sum(X) = sum(A) * x/N

을 제공하므로 오른쪽도해야합니다. 이것은 T_k = S * k/N이 정수 여야한다는 제약을 유발합니다. 유일한 나머지 부분은 크기 k의 서브 세트의 합으로서 T_k을 실현하는 것입니다.

출처

2012-01-18 19:07:47 PengOne

입니다. 당신의 증명이 OP의 문제에 대한 부분 집합 합계를 어떻게 줄이는 지 아직 볼 수 없습니다. – soulcheck

내 말은, 당신은 essencially OP의 문제에 대답 할 수있는 부분 집합 합계에 대한 답변을 가지고 있다는 것을 증명했습니다. – soulcheck

@soulcheck 나는 그들이 진정으로 동등한 지에 대해 아직도 숙고하고있다. 대답은 [내가 방금 요청한이 질문] (http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size)에 달려 있다고 생각합니다. – PengOne

두 부분의 평균이 같도록 배열을 두 부분으로 나누는 방법은 무엇입니까?

답변

관련 문제