Q&A
商品A1個と商品B1個が入る最小の箱を箱１、箱2、、、から探すという処理ですか？それともはAとBは複数入れる前提で？最後にAとBは向きは変えたらだめという条件ですか？
###前提・実現したいこと
PHPでシステムを作っております。
下記アルゴリズムを作成するにあたり、何か良い案はありますでしょうか？
数学の得意な方、ご回答お待ちしております。
ーーーーーーーー
・大きさが違う商品Aと商品Bがあります。
・大きさが違う箱が複数あります。
・この時、商品Aと商品Bがぴったり入る箱を求めるには、どのようにしたら良いでしょうか？
また、可能であれば、商品が増減しても求められる数式があればご教示願いたく思います。
例）
項目・・・ 幅, 奥行き, 高さ
商品A・・・ 100, 70, 80
商品B・・・ 80, 50, 70
箱1・・・ 100, 80, 60
箱2・・・ 120, 100, 80
箱3・・・ 140, 120, 100
箱4・・・ 160, 140, 100
箱5・・・ 180, 160, 120
箱6・・・ 200, 180, 120
箱7...
箱8...
・
・
・
商品は回転（？）可能ですか？ 天地が横になるのはまずいとか？
商品Aがn個、商品Bがn個で、全てが入る最小の箱を探すという処理になります。また、向きが変わるのも、天地が横になるのも可能です。
これってNP完全問題だったりしませんか。箱と商品の大きさに規格があるなら違うかもしれないが
回答4件
0
私は数学が得意でないので、参考程度の回答となりますが、、
これは「ビンパッキング問題」というものですね。
Wikipediaの解説を読む限り、一筋縄ではいかない問題のようです。
https://ja.wikipedia.org/wiki/%E3%83%93%E3%83%B3%E3%83%91%E3%83%83%E3%82%AD%E3%83%B3%E3%82%B0%E5%95%8F%E9%A1%8C
様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。
「３次元 パッキング」
などのキーワードで検索すると以下のようにいろいろ見つけることができますが、いずれも私には、何をやっているのか分かりませんでした(^^;
http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1726-05.pdf
http://www.seto.nanzan-u.ac.jp/ise/gr-thesis/ms/2010/07mi030.pdf
投稿2016/11/11 03:41
総合スコア4791
0
箱を絞り込む所までは思いつきましたので一応書いておきます
1.全商品が絶対に収まらない箱を除外する
これは単純に各商品の容積を計算しそれに個数をかけたものと
箱の容積を比較すれば分かると思います
全商品の商品の容積を箱の容積が下回れば
その箱に入るという事はありません
ただし
逆に箱の容積が全商品の容積を上回ってさえいれば
必ず収まるとは言えません
2.全商品が必ず収まる「最小の箱」を求める（アルゴリズムA）
2つの商品のサイズ縦横高さを大きさ順にソートして
各順位同士を比較することでどちらかの商品サイズに
もう一つが収まるか否かという事が分かります
これを利用して例えば下記のように3つの商品がある場合
商品A 100 120 70
商品B 110 50 110
商品C 90 80 100
これをソートします（ここでは昇順にソートします）
（商品A 100 120 70 は 70 100 120 となります）
商品A 70 100 120
商品B 50 110 110
商品C 80 90 100
これを縦列で見ていくと
全商品が必ず1個は収まる「最小の箱」は
80(70 50 80で最大)
110（100 110 90で最大）
120（120 110 100で最大）の組合せとなります
3.「最小の箱」を使って全商品が収まるかどうか検討
まずある直方体の中にもう一方の直方体が
最大何個収まるのか決定するアルゴリズムを考えます（アルゴリズムB）
ある向きの直方体A（サイズa×b×c）が
もう一つの直方体B（サイズx×y×z）の中に何個収まるかは
切り捨てをする関数floor( )を使って下記の式で求められると思います
floor(x/a)*floor(y/b)*floor(z/c)
箱の向きは6通りあるので残りの個数も求めます
floor(x/a)*floor(y/c)*floor(z/b)
floor(x/b)*floor(y/a)*floor(z/c)
floor(x/b)*floor(y/c)*floor(z/a)
floor(x/c)*floor(y/a)*floor(z/b)
floor(x/c)*floor(y/b)*floor(z/a)
これらの中で最大値となるのが収まる直方体の最大値です
これを利用してまず「最小の箱」に収まる商品ごとの最大の個数を求めます
商品ごとの最大の個数が求まったら
それに応じた全商品を納めるための「最小の箱」の個数を求めます（アルゴリズムC）
例えば最大の個数が 商品A 1個 商品B 2個 商品C 4個だとすると
商品の個数がそれぞれ(A 5,B 6,B 7)個だったとして
切り上げをする関数ceil()を使って
ceil(5/1) + ceil(6/2) + ceil(7/4)
となり
5 + 3 + 2 となり
全商品を納めるためには10個の「最小の箱」が必要になると思います
必要な「最小の箱」の数が求まったら
それがおさまるものを箱のリストの中から探索します
（やり方は商品が「最小の箱」に何個収まるのか求めたのと全く一緒です）
4.無駄無く納めるために組合せを考える（アルゴリズムD）
必要な容積最小の箱と「最小の箱」が収まる最小の箱の間に
求める箱はあるのだと思いますが
これを探索するのは箱同士の立体的な組合せを考えなければならず
普通に組合せで解こうとすると商品が2・3個のうちは良いが
10個を越えるとお手上げとかそんな類いの問題のような気がします
多分この問題はNP完全かNP困難かといった問題であり
ヒューリスティックに解くしか無く
厳密解は出てこないと予想します
（あくまで予想で証明はできないのですが）
「直方体 充填 アルゴリズム」とかで検索すると
良いものが見つかるかもしれません
※イメージしやすいように図をつけました
文字だけだとわかりにくいですよね
投稿2016/11/11 11:15
編集2016/11/13 01:43
総合スコア284
0
商品Aと商品Bだけなら、３辺が 70X 80Y 50Z (X,Y,Zは１以上の整数）の箱にぴったり入ります。
これは商品Bが商品Aの半分の大きさだから、解のひとつが簡単に見つかりました。
いろんな方向に回転させた商品を隙間なく詰められる事は、稀です。
質問の商品Aと商品Bだけなら、商品は高さが70になるように置くことにして、高さが70A,縦と横がそれぞれ400(80,50,100の最小公倍数）B,400C (A,B,Cは１以上の整数）の箱に詰めるなど、構成的に求めていった方が容易だと思います。
パズルのように全ての解が求められる訳ではありませんが、商品を詰める方法を説明するのが簡単なので実用的だと思います。
注）「ぴったり」というのを隙間なく入れることが出来る事と解釈して回答しています。
投稿2016/11/11 05:02
総合スコア6919
0
質問の意図とズレるかもしれませんが、
ビジネスの実務において、この手の最適化問題は、
数学的な正解を求める必要はない（または求められない）ことが多いです。
すなわち、ナップサック問題のようなNP困難問題には、
ヒューリスティックな解で満足することが多いです。
そこで、遺伝的アルゴリズムなどの確率的な探索を行います。
それでは、少し具体的な実装のイメージを言いましょう。
まず、実務的な問題には、必ず値段などのコストが関係するはずです。
もし、箱のコストがゼロなら、最大の箱に全部詰めても問題ないはずですから。
ですから、詰められる数は最大、箱のコストは最小、
になるとスコアが高いように評価関数の式を立てます。
（詰める数とコストの優先順位などの条件で、式は異なってきます）
それで、どの箱を何個買うかという選択を遺伝子にして、
遺伝的アルゴリズムのプログラムを組みます。
後は、回答の精度と計算量のトレードオフの問題です。
これは「すべての商品が入る最小の箱」という題意とは微妙に違いますが、
現実には複数の箱を買った方が安くつく場合が多いので、
潰しが利く考え方として参考までに述べました。
もちろん、数学的な解析でキレイに解を出せる場合もありますが、
ちょっと条件が変わるだけですぐ通用しなくなる場合が多いので、
汎用的に使える遺伝的アルゴリズムが何かと便利です。
ちなみに、商品の数が少ないとかで、計算量が実時間に収まる場合には、
Prologなどでの論理プログラミングで直接解いてしまう手法もあります。
まあこれもPHPではないんですが、実務では使われているので参考までに。
投稿2016/11/12 13:00
総合スコア5592
あなたの回答
tips
プレビュー
