같은 크기의 빈 넣기

Question

나는 100 개의 그룹이 있으며 각 그룹에는 내부에 몇 개의 요소가있다. 교차 유효성 검사를 위해 가능한 한 크기가 같은 5 개의 저장소를 만들고 싶습니다.

이 목적을위한 알고리즘이 있습니까?

5 개 그룹 및 2 빈들의 예 :

Group_1: 5 
Group_2: 6 
Group_3: 2 
Group_4: 7 
Group_5: 1 

두 빈들

될 것이다

G1 및 G2 -> 그 합이 동일

11 G3, G4 및 G5 -> 합이 10입니다.

Answer 1

set partitioning problem과 관련이있는 것 같습니다. NP -hard이지만 다행스럽게도 g ood 근사 알고리즘 및 의사 다항 시간 동적 프로그래밍 알고리즘을 사용합니다. 이미이 분야에서 많은 일들이 진행 되었기 때문에 출발점으로 삼고 싶을 수도 있습니다.

희망이 도움이됩니다.

Answer 2

크기 제한이 동일한 클러스터링 알고리즘 (파티셔닝 방법)을 찾으려면 스펙트럼 클러스터링을 제안하십시오. 균형 잡힌 절단을 찾기 위해 정규화 된 절단 문제를 해결하므로 거의 동일한 크기의 클러스터에 대한 사용자의 요구를 충족시킵니다.

Answer 3

이것은 cluster analysis 문제가 아닙니다. (나는 당신에게보다 적절한 문구를 사용하기 위해 질문을 다시 작성했습니다). 클러스터 분석은 구조 검색 작업입니다.

• Multiprocessor scheduling 당신이 필요한 것 같다 : 대신

  , 컴퓨터 과학에서 다음과 같은 두 가지 관련 문제를 살펴있는 최소한의 시간이 사용되지 않도록 작업을 배포, 주어진 n 개의 프로세서를

• Bin packing problem은 고전적인 NP 하드 문제로 역의 문제를 해결합니다. 고정 된 크기의 빈을 모든 작업에 사용할 수 있습니다.
• k-Partition Problem 아마도 이것은 사용자가 원하는 작업 일 것입니다.

이 모든 당신이 단지 근사치를 사용하려면 있도록

(용량이 큰 데이터가있는 경우 당신이 할 수있는 단지 5 예 쉽게 무차별 모든 조합), NP-어려울 것으로 보인다