人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

数学の質問です。
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にはいらなかったりします。

●質問者: kouryukai
●カテゴリ:ビジネス・経営 学習・教育
✍キーワード:A.B.C. E60 数学 花子 計算
○ 状態 :終了
└ 回答数 : 3/3件

▽最新の回答へ

1 ● momoescythe
●100ポイント

http://hp.vector.co.jp/authors/VA008160/cipher/knap.htm

ナップサック問題

http://ja.wikipedia.org/wiki/%E3%83%8A%E3%83%83%E3%83%97%E3%82%B...

ナップサック問題 - Wikipedia

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


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

◎質問者からの返答

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

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

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

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

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


2 ● akagi_paon
●100ポイント

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など)があるとは思いますが、ここで説明できる

ものではありません。

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

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

◎質問者からの返答

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

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

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


3 ● くまいみずき
●20ポイント

http://www.google.com/

Google

まず、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の値をかえれば求められます。

◎質問者からの返答

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

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ