需要算法將不同大小的文件分組成大致相等的塊

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 means可能會幫助你。研究更高級的聚類算法是一個很好的起點，但考慮到你的問題是一維的，k-means應該足夠了。

Answer 3

您的隱式優化目標很可能會最小化組數。那麼你就有bin packing problem，有時也叫做cutting stock problem。

Netlib有這個fortran code來解決更一般的多揹包問題（物品有利潤以及成本/重量值）。