알고리즘 : 모든 하위 목록 사이의 요소 합계의 최대 차이를 최소화하여 값 목록을 하위 집합으로 구분하십시오.

Question

B 비어 있지 않은 하위 목록을 변경하지 않고 값의 목록 (정수)을 가지고 있습니다. 그들의 초기 주문. 목표는 텍스트의 크기를 정의 된 영역에 맞게 조정하는 것입니다.

각 하위 목록에는 하나의 메트릭, 즉 해당 값의 합계가 연결됩니다. 의 차이를 최소화하고 싶습니다. DIFF사이의 가장 큰 합계와 가장 작은 합계는 모두입니다. 이것은과 거의 동일한 양의 줄로 텍스트를 나누는 으로 나를 허용 할 것입니다.

편집

제안한 것처럼, 그것은 또한 그 텍스트 행의 최대 길이를 최소화 초래으로, 최대 합을 최소화하기 위해 작동합니다.

예 :

주어진리스트 L = {2,3,4,5,6} 및 B = 2

해결책 : L1 = {2,3,4} 및 L2 = {5,6}. SUM (L1) = 9, SUM (L2) = 11 = DIFF리스트 L = {1,1,8,1,1,1,8,1} 및 B 주어 2

---

= 3 L1 = {1,1,8}, L2 = {1,1,1} 및 L3 = {8,1} .Sum (L1) = 10, Sum (L2) = 3, Sum (L2) = 12, L3) = 9 DIFF = 7

내가 IT 배경을 가지고 있지 않기 때문에, 나는이 접근하는 방법을 잘 모르겠어요

나의 제안. 먼저, 원래 세트를 두 세트로 나눌 수있는 조합 수를 알아 내려고 시도했습니다 서브리스트.

그럼 I는를 찾아 적절한 알고리즘 것을 확인하려 : 원래 목록의 요소 수가 N은 다음 가능한 분할의 수있을 것 인 같 전역 최소. 아래 두 가지 조건이 모두 존중되는 상황에 처했을 때 전 세계 최저 수준에 도달했을 것이라고 생각했습니다. 로의 요소 (중 하나)의 가장 큰 하위 목록 (들) (한) 이웃 (들)을 이동

는

• DIFF이 향상되지 않습니다.
• 가장 작은 하위 목록 중 하나의 요소를 이웃 요소 중 하나로 이동하면 DIFF이 향상되지 않습니다.

는

이 보증에 충분한 언급 한 두 가지 조건이 있습니까

질문합니다 (하위 목록은 비워 둘 수 없습니다로서, 하나의 요소와 하위 목록에서 요소를 이동하는 여러 하위 목록을 변경할 필요) 전체 최소 (DIFF의 경우)?

이 문제를 해결하는 알고리즘을 알고 계신가요? 아니면 이것을 해결할 제안이 있습니까?

이런 종류의 문제를 해결하는 데 도움이되는 독서 권장 사항이 있습니까?

내가 말했듯이, 나는 배경이없고 그러한 컴퓨터 이론 문제에 대한 많은 경험이 없다.

감사합니다.