最適なファイルの組み合わせを見つけるコツ
どのファイルを組み合わせれば目的の容量に最も近づくのかという問題は、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 |
3 |
ファイル7 |
50MB |
|
ファイル8 |
53MB |
|
ファイル9 |
100MB |
2 |
ファイル10 |
103MB |
1 |
1+2+3で234MBになります。目標の247MB−234MB=7MBですから、残りは小さい似たようなサイズのファイルの組み合わせを行います。
ファイル1 |
1MB |
6 |
ファイル2 |
2MB |
5 |
ファイル3 |
4MB |
4 |
ファイル4 |
8MB |
|
ファイル5 |
30MB |
|
ファイル6 |
31MB |
3 |
ファイル7 |
50MB |
|
ファイル8 |
53MB |
|
ファイル9 |
100MB |
2 |
ファイル10 |
103MB |
1 |
を選べばちょうど247MBに収まりました。
また、適当に、
ファイル1 |
1MB |
|
ファイル2 |
2MB |
|
ファイル3 |
4MB |
6 |
ファイル4 |
8MB |
5 |
ファイル5 |
30MB |
4 |
ファイル6 |
31MB |
|
ファイル7 |
50MB |
3 |
ファイル8 |
53MB |
2 |
ファイル9 |
100MB |
|
ファイル10 |
103MB |
1 |
と選んだ場合、248MBとなり1MBオーバーしてしまいます。
このときは、容量が似たようなファイルのグループ(ファイル1〜4、5〜6、7〜8、9〜10)の中から、1MB減らせそうな組み合わせを探します。
ファイル1 |
1MB |
|
ファイル2 |
2MB |
B |
ファイル3 |
4MB |
6 |
ファイル4 |
8MB |
5 |
ファイル5 |
30MB |
4 |
ファイル6 |
31MB |
|
ファイル7 |
50MB |
3 |
ファイル8 |
53MB |
2 |
ファイル9 |
100MB |
A |
ファイル10 |
103MB |
|
何度か試行錯誤して、1をA+Bに置き換えてみると、ちょうど247MBにすることが出来ました。
以上のように、ファイルの総容量を微調整するには「容量が似たようなファイルのグループ」がキーワードとなります!
また、103MBの単体ファイルを50MBと53MBの複数別ファイルに置き換えてみたりすることも重要です。
最初は適当に選んで、後から大まかな調整→細かな調整と精度を上げていくのが、もっとも効率が良いです。
☆もし、数学に詳しい方で計算量もそれほど多くなく解が導ける解法が分かる、という方がおられましたら是非実装したいので作者まで連絡ください!