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はあなたを助けるかもしれないことを意味します。より高度なクラスタリング アルゴリズムについて調査するのは良い出発点ですが、問題が 1 次元であることを考えると、k-means で十分です。

Answer 3

あなたの暗黙の最適化目標は、グループの数 n を最小化する可能性が最も高いです。次に、まさに、カッティング ストック問題と呼ばれることもあるビン パッキング問題が発生します。

Netlib には、より一般的な複数のナップザックの問題を解決するためのこのfortran コードがあります (アイテムには利益とコスト/重量の値があります)。