algorithm - 需要算法将不同大小的文件分组为大致相等的块

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 意味着可能会帮助你。这是研究更高级聚类算法的一个很好的起点，但鉴于您的问题是一维的，k-means 应该绰绰有余。

Answer 3

您的隐式优化目标最有可能最小化组数 n。然后就是装箱问题，有时也称为切割库存问题。

Netlib 有这个fortran 代码来解决更一般的多重背包问题（项目有利润以及成本/重量值）。