数学の質問です。

A.B.C.D.Eという形の違う箱を売り出しました。早速3人から注文が入りました。(太郎、次郎、花子)
商品をXという箱に入れて発送しようと思います。
上記のような場合どのような計算を使えばよいのでしょうか。
求めたい値はXが何箱必要かです。
例えばA 20*30*40 B 20*30*60 C 20*30*75 D 35*40*80 E60*25*40
X 150*150*300
太郎 A20 C30 E35
次郎 A30 B25 D25
花子 B30 D15 E15
例を使ってもよいですし、使わなくてもよいです。体積で計算すると実際にXにはいらなかったりします。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2006/02/24 04:53:52
  • 終了:--

回答(3件)

id:momoescythe No.1

momoescythe回答回数7ベストアンサー獲得回数02006/02/24 05:58:00

ポイント100pt

こちらの問題は、いわゆる「ナップサック問題」を3次元に拡張したものと考えることができます。「ナップサック問題」は一般に困難な部類の問題であるため、しらみつぶしに探すしかなく、動的計画法などにより効率よく計算することで高速化をすることは可能ですが一瞬で求まるような計算方法は現時点ではないと思われます。


さて、この問題に関してですがXの数を最小化するということは前提として、3人というのは意味があるのでしょうか?(例えば3人の注文は別な箱でなければならない等。)また、箱は体積的に詰め込むことが可能なら詰め込んでも良いのでしょうか?(斜めに無理やり押し込める等)特に、後者を認めると、探索が際限なく増えて、解くことが現実的に非常に難しくなるような気がします。

id:kouryukai

回答ありがとうございます。

まず3人という意味はありません。問題を簡略化するために3という数字を使っただけです。

商品なので詰め込みもなしです。

実はこのような仕事で悩んでいまして、注文者数が300前後だったり、商品数が30種類だったりします。

いつもはその場しのぎで、箱に詰めて、その都度伝票に中身を記載しています。

2006/02/24 06:03:07
id:akagi_paon No.2

akagi_paon回答回数143ベストアンサー獲得回数132006/02/24 09:19:48

ポイント100pt

http://www.hatena.ne.jp/1140724432#

人力検索はてな - 数学の質問です。 A.B.C.D.Eという形の違う箱を売り出しました。早速3人から注文が入りました。(太郎、次郎、花子) 商品をXという箱に入れて発送しようと思います。 上..

ええと、おそらくビンパッキング問題が解きたいんじゃないかと。


つまり、n 個のサイズの品物をサイズ X の箱に詰め込むとき、

使用する箱の個数を最小にする詰め込み方を求めたいという問題です。


この問題は上の方もおっしゃっているように現在のコンピュータでは

最適な解を求めるには全てのパターンをしらみつぶしに調べるという

方法しか発見できておらず、解くのにものすごく時間がかかってしまう

というたぐいの問題です。


そこで、このような問題を解く場合、最適解ではなく近似解を求める

という方法が一般的にとられます。

つまり、本当は4個の箱に収まるかもしれないけど、その方法を求める

のが難しいので、空間に多少の無駄はでるかもしれないけど5個の箱に

収める方法を導くといった具合です。


いちばん簡単な方法は First-Fit という方法で、

詰め込みたい品物を適当な順番で箱に入れてゆき、

入らなくなったら新しい箱を出すという方法です。

当然のことながら、新しい箱を出したあとでも、

古い箱に詰め込むことができるときはそうします。

(もしかしたら今までもこんな感じでやってきたのでは?)


このようにやると、箱の個数は最適解の2倍以内に収まることが

証明されています。

つまり、一番うまく詰め込むと4個の箱で済むという場合に、

必ず8個以内に収めることができるというわけです。


「2倍」というのは大きすぎると思われるかもしれませんが、

「2倍以内」であり、必ず2倍になるということではありません。

この方法で一番最適な詰め込み方になる可能性もあります。


(さらに言うと、この問題には最高でも1.5倍以内に収める解法しか

 存在しない(つまり、例えば1.4倍以内に収める解法は無い)ことが

 知られているのと、箱の数が多い場合は First-Fit は1.7倍以内に

 近づくいていくということを合わせて考えれば単純ながら結構いい

 方法だと思えてきませんでしょうか)


もっといい方法(PTASなど)があるとは思いますが、ここで説明できる

ものではありません。

専門家に相談すれば、個別なパラメータ(品物のサイズがだいたい

決まっているとか)を使っていい解法を作ってくれるかもしれませんよ。

id:kouryukai

やはり最適な解答を一発で出すことはできないのですね。

色々な手法があるものですね。

とても参考になりました。

2006/02/24 12:43:31
id:kumaimizuki No.3

くまいみずき回答回数614ベストアンサー獲得回数312006/02/24 09:35:30

ポイント20pt

まず、A~Eと箱(X)の関係を調べます。

縦と横、高さだけを比べて、各商品が箱にいくつ入るか求めます。


例)

Aの場合

縦:7個(Xの縦(150)÷Aの縦(20))

横:5個(Xの横(150)÷Aの横(30))

高:7個(Xの高(300)÷Aの高(40))


いずれも小数点以下切り捨てです。


数が多いそうですが、これならExcelで簡単に求められますし。


A1:150(箱の縦)

B1:150(箱の横)

C1:300(箱の高)


A2:20(Aの縦)

B2:30(Aの横)

C2:40(Aの高)


この状態でA3セルに「=rounddown(A1/B1, 0)」と入れると、入る個数が分かります。

次に、最小値を求めます。

D2セルに「=min(A2:C2)」と入れると最小値が求められます。

これが箱に入る個数となります。

商品ということで、他の商品を詰め合わせなければ、これで個数が求められます。


例)Aという商品の場合

最大で5個入るということで・・・


太郎さん(20個)=4箱

次郎さん(30個)=6箱

花子さん(30個)=6箱


となります。


仮に箱の種類が複数ある場合でも、シートをかえて、A1~C1の値をかえれば求められます。

id:kouryukai

とてもわかりやすい解答ありがとうございます。

2006/02/24 19:16:31

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません