最適なファイルの組み合わせを見つけるコツ


どのファイルを組み合わせれば目的の容量に最も近づくのかという問題は、NP問題の一つだと思われます。
一見簡単そうに見えて、実は解くのが難しい問題です。
このソフトが組み合わせの発見を全自動でやらないのも、この解法が私には分からないからです(笑)

しかし、経験的に最適なファイルの組み合わせを見つけるコツというものを編み出しましたので、試してみてください。

一般的にファイルが沢山ある場合、サイズの大きなファイルから小さなファイルまで様々あり、また似たようなサイズのものが結構含まれます。

例えば、次のようなファイルがあるとします。
ファイル1 1MB
ファイル2 2MB
ファイル3 4MB
ファイル4 8MB
ファイル5 40MB
ファイル6 41MB
ファイル7 80MB
ファイル8 83MB
ファイル9 100MB
ファイル10 103MB

ここで、容量を247MB以下に収めたいとします。

とりあえず、大きいサイズのものから適当に選んでいきます。(表右端の数字が適当に選んだ順番)

ファイル1 1MB
ファイル2 2MB
ファイル3 4MB
ファイル4 8MB
ファイル5 30MB
ファイル6 31MB
ファイル7 50MB
ファイル8 53MB
ファイル9 100MB
ファイル10 103MB

1+2+3で234MBになります。目標の247MB−234MB=7MBですから、残りは小さい似たようなサイズのファイルの組み合わせを行います。

ファイル1 1MB
ファイル2 2MB
ファイル3 4MB
ファイル4 8MB
ファイル5 30MB
ファイル6 31MB
ファイル7 50MB
ファイル8 53MB
ファイル9 100MB
ファイル10 103MB

を選べばちょうど247MBに収まりました。

また、適当に、

ファイル1 1MB
ファイル2 2MB
ファイル3 4MB
ファイル4 8MB
ファイル5 30MB
ファイル6 31MB
ファイル7 50MB
ファイル8 53MB
ファイル9 100MB
ファイル10 103MB

と選んだ場合、248MBとなり1MBオーバーしてしまいます。
このときは、容量が似たようなファイルのグループ(ファイル1〜4、5〜6、7〜8、9〜10)の中から、1MB減らせそうな組み合わせを探します。

ファイル1 1MB
ファイル2 2MB B
ファイル3 4MB
ファイル4 8MB
ファイル5 30MB
ファイル6 31MB
ファイル7 50MB
ファイル8 53MB
ファイル9 100MB A
ファイル10 103MB

何度か試行錯誤して、1をA+Bに置き換えてみると、ちょうど247MBにすることが出来ました。


以上のように、ファイルの総容量を微調整するには「容量が似たようなファイルのグループ」がキーワードとなります!
また、103MBの単体ファイルを50MBと53MBの複数別ファイルに置き換えてみたりすることも重要です。
最初は適当に選んで、後から大まかな調整→細かな調整と精度を上げていくのが、もっとも効率が良いです。

☆もし、数学に詳しい方で計算量もそれほど多くなく解が導ける解法が分かる、という方がおられましたら是非実装したいので作者まで連絡ください!