×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

ビンパッキング問題

ビンパッキング問題は、与えられた荷物をできるだけ少ない箱(ビンやコンテナ)に詰める問題です。
例えば、荷物を詰めるコンテナがあり、そのコンテナには一定の重さまでしか荷物を詰め込めないとします。
この時、重さの異なる複数の荷物をどうやってコンテナに詰めれば、コンテナの数を少なくできるかを求めるのが、ビンパッキング問題です。

Wikipedia「ビンパッキング問題」を参照してください。

項目に荷物の重さ(カンマ区切りで複数指定)を入力し、容量にビンに詰め込める最大の重さを指定し、実行ボタンを押すと、どのように詰め込んだら良いかが下のボックスの表示されます。

表示される結果ですが、1行が一つのビンを表しています。[] に表示されるのが、ビンに入る荷物の重さ、: の右側が、その合計の重さとなります。

この問題を解く万能なアルゴリズムはないということで、近似解を求めるアルゴリズムを書くことになるのですが、ここで書いたプログラムでは2つのアルゴリズム(正確には3つ)を使っており、その2つの良い方を解としています。

 一つ目のアルゴリズムは、最も空きが多いビンに荷物を入れてゆく解法(Solve01)
二つ目のアルゴリズムは、「最も空きが少ないビンに入れてゆく解法(Solve02)」を繰り返し適用する方法(Solve03)
です。この二つ目のアルゴリズムはGushwellが独自に考えたものです。
詳しくはソースを見てくださいね。
 
内部で LINQを使っていますが、それほど難しいことをしてるわけではないので、何をやっているかは、コードとコメントを読んでいただければ、容易に理解できると思います。
 
ソースには、4つ目のアルゴリズム Solve04も載せています。アルゴリズム1の変形バージョンです。
興味がある方は、Solve04も動かしてみてください。


以下に、C#+Silverlightのコードを示します。
BinPacking.csは、Silverlightには依存していません。


■BinPacking.cs


■MainPage.xaml.cs
 

■MainPage.xaml