다양한 크기의 파일을 거의 같은 크기의 'n'그룹으로 그룹화하는 데 도움이되는 알고리즘을 이해하려고합니다.다양한 크기의 파일을 대략 동일한 블록으로 묶을 수있는 알고리즘이 필요합니다.
달성 방법에 대한 아이디어가 있으십니까?
다양한 크기의 파일을 거의 같은 크기의 'n'그룹으로 그룹화하는 데 도움이되는 알고리즘을 이해하려고합니다.다양한 크기의 파일을 대략 동일한 블록으로 묶을 수있는 알고리즘이 필요합니다.
달성 방법에 대한 아이디어가 있으십니까?
Find the target group size. This is the sum of all sizes divided by n.
Create a list of sizes.
Sort the files decreasing in size.
for each group
while the remaining space in your group is bigger than the first element of the list
take the first element of the list and move it to the group
for each element
find the elemnet for which the difference between group size and target group size is minimal
move this elemnt to the group
이렇게하면 최적의 결과는 나오지 않지만 구현하기 쉽고 좋은 결과를 얻을 수 있습니다. 최적의 솔루션을 얻으려면 NP 완성 검색이 필요합니다.
K means 당신을 도울 수 있습니다. 고급 클러스터링 알고리즘에 대한 연구를 시작하기에 좋은 출발점이지만 문제가 1 차원이기 때문에 k- 평균은 충분해야합니다.
내재적 최적화 목표는 그룹 수인 n을 최소화하는 것이 가장 좋습니다. 그런 다음 정확히 bin packing problem이고 cutting stock problem라고도합니다.
Netlib는보다 일반적인 다중 배낭 문제 (항목은 비용/중량 값으로 이익도 있음)를 해결하기 위해 fortran code을 가지고 있습니다.
K- 평균을 사용하여이 문제를 어떻게 푸시겠습니까? OP는 "비슷한 크기의 그룹"을 원하지만 비슷한 크기의 아이템이 포함 된 클러스터가 아닙니다. – bubaker
흠 ... 확실합니까? op가 두 개의 서로 다른 컨텍스트에서 크기를 사용한다면 좀 더 명확해야합니다. -/어쨌든보다 적합한 클러스터링 방법을 찾는 것이 좋은 출발이라고했습니다. – fortran