3次元箱詰め問題プログラミング
押入れで無造作に積まれているフィギュアを、きれいにケースに入れて整理したいと思い、久しぶりにVBAでプログラムを書いた。
押入れにぴったり合うサイズの収納ケース、天馬のフィッツケースシリーズの中に、フィギュアを効率よく（無駄なスペースを少なくするように）詰めていくことを目的としている。
深く検討せずに、えいやで構築したので改善の余地が多分にあるが、動いたのでとりあえずはよしとする。
フィットケースの種類ごとに幅、奥行き、高さのデータを用意。詰めるフィギュアの箱のサイズデータも同様に別シートに用意。
今回のアルゴリズムは以下の通り。
- 大きなフィギュアからなるべく小さいケースに詰める
- 詰める際の優先順位は左から右、手前から奥、下から上
- すでに使用中のケースがある場合は空きスペースに入るかチェック
- 使用中のケースに入らなければ新しいケースを用意
- 123をすべてのフィギュアに対して繰り返す
- 結果を出力
今回は、サイズをcmで採寸した。1cm3(立方センチメートル)を1単位とし、ケースの幅、奥行き、高さを多次元配列で用意。VBAは多次元配列が簡単に用意できるのが便利。配列のデータ数は実際のケースのサイズよりも大きくなるよう準備した。これは、ケースのサイズが数種類あることに対応するためと、当たり判定時にはみ出した部分でインデックス外エラーとなるのを防止するためである。
データ上、0で初期化された200×200×200の大きな配列の箱に実際に使うケース部分を別の数字(2など)で上書き。これで、2の格納された部分がケース、0はケース外と判定できる。
フィギュアの箱はさらに別の数字(1など)で表現。詰めた場所は1で上書きする。次に別のフィギュアを詰めるときは、1でも0でもない2の場所が、フィギュアの箱のサイズ分確保できる始点を探す。別途、どのフィギュアをどのケースのどの座標を始点に、どの向きで置いたかを結果出力用に記録。
フィギュアを詰める際は、フィギュア箱の置き方が6通りあるため、とりあえず入る場合が見つかった時点で探索終了とした。ベストな詰め方を見つけるには、全ての入る場合を検討する必要があるのだが、探索数が増えてしまうのと、簡単に書くことができるやり方が出てこなかったので不採用。今の状態をメモっておき、再帰的に探索をすすめて、容積率や箱のサイズ、金額などで最も効率的と思われる方法を解とするのが現実的か。
実際に動かしてみた結果、フィッツケースを使うと今の場所だけでは収まらないことが判明。悲しいが、仕方がない。買ってから気づくよりはよかったか……
ここ最近まで、プログラムを書こうという気力が全く湧いてこなかったが、久しぶりに手を動かすとやっぱり楽しい。エラーを吐いたときに原因を探るワクワク感、無駄を省いてソースが洗練されていく喜び、初めて設計通りに動いたときの感動、どれも健在。次は何を作ろうか。
