다양한 크기의 파일을 대략 동일한 블록으로 그룹화하려면 알고리즘이 필요합니다.

Question

나는 다양한 크기의 파일을 대략 같은 크기의 'n'그룹으로 그룹화하는 데 도움이되는 알고리즘을 알아 내려고 노력하고 있습니다.

이것을 달성하는 방법에 대한 아이디어가 있습니까?

Answer 1

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가 완료된 철저한 검색이 필요합니다.

Answer 2

k는 도움이 될 수 있습니다. 고급 클러스터링 알고리즘에 대한 연구에 대한 좋은 출발점이지만 문제가 1 차원이라는 점을 감안할 때 K- 평균은 충분해야합니다.

Answer 3

암시 적 최적화 목표는 그룹의 수를 최소화 할 가능성이 높습니다. 그럼 당신은 정확히 있습니다 빈 포장 문제, 때때로 재고 문제 절단.

Netlib은 이것을 가지고 있습니다 포트란 코드 보다 일반적인 다중 배제 문제를 해결하기 위해 (품목은 비용/무게 가치도 있습니다).