数学の問題？ 板を効率よく切り分けたいです。

質問

180センチ×90センチの板をカットして、希望の寸法に切り分けたいです。

カットしたい寸法は7種類あります。

a. 47.6 * 44 ・・・16枚
b. 49 * 16 ・・・16枚
c. 46.4 * 16 ・・・16枚
d. 47.6 * 16 ・・・32枚
e. 150 * 60 ・・・4枚
f. 150 * 49.1 ・・・2枚
g. 58.8 * 49.1 ・・・18枚

(単位は全てセンチメートル)

余り(端材)を可能な限り少なくなるように切るには、どのような組み合わせが最も効率がいいでしょうか？
求め方の計算式がありましたら教えてください。
なお、切りしろは5mmとします。

回答No.5

maiko0318 · ベストアンサー

作ってみました。１４枚ですね。

添付できないのでHPにアップしました。

http://www.eonet.ne.jp/~fhm07425/shuu_01.pdf

１／１０スケールで作っています。
作業に掛かる前に大きさと枚数を確認して下さいね。

お礼

14枚で済むのですね。
作って下さったファイル、有難く頂戴致します。
大変感謝です！

回答No.18

okormazd

いわゆるナップザックのような問題で、計算式は無いでしょう。工夫して効率よく組み合わせを調べていくというやり方です。部材の形と数からそれほど難しいことは無いと思いますが、下記でどうでしょう。

e、f、gは、いずれも90cm巾方向で2枚はとれません。したがって、180cm方向でとるしかない。したがって、これらを指定枚数とるのに180cmが何枚必要かというのが最低枚数です。VBAでExcelソルバーを使って解く(試行錯誤のプログラムです)と、最低12枚は必要です。b、c、dはこのうちにとれるでしょう。たぶん、66枚とれる。あとは、aをとればいい。

e1-4枚
f1-2枚
g3-6枚

a6-2枚
a4-1枚

計15枚か。これより少なくは無理でしょう。

お礼

やはり計算式はないのでしょうか。
VBAやEXCELなどで試行錯誤してみようと思います。
回答をありがとうございました。

回答No.17

shuu_01

No.5、No.16 さん、回答ありがとうございます

やはり、ケアレスミスはあったけど、No.5 さんの回答すごいです

僕も最初なんで 18枚となったか再検討するとケアレスミスでした

No.5 さんの描かれた図をじっと見ると、

大きな部材　　　　　　　：　e、f
（母材から１つしか取れない）
次に大きな部材　　　　：　g
（母材から３つしか取れない）
その次に大きな部材　：　a
（母材から６つしか取れない）
小さな部材　　　　　　　：　b、c、ｄ
（上記の余りから取れる）

に分けられ、

e を ４枚とるのに　母材 ４枚
f を ４枚とるのに　母材 ２枚
g を １８枚とるのに　母材 ６枚
a を １６枚とるのに　母材 ３枚

の合計 最低 １５枚は必要で ＝ １４枚以下はありえず、

その余りから 小さな部材 b、c、d は十分 取れちゃうようです

お礼

とても論理的な分析をして下さり、ありがとうございます。
この考えを基に検討すれば効率的に取ることができそうで、大変助かっております。
この度はご教示を下さいまして、本当にありがとうございました！！！

回答No.16

maiko0318

no.10さん、
＞そこで確認してみましたが、g が本来 18枚 なのですが、15枚しかないのでは？

間違っているようです。ごめんなさい。＞NO10さん、質問者さん。

お礼

とんでもないことです。
回答を下さいまして、大変助かっております。
この度は本当にありがとうございました。
感謝、感謝です！！！

回答No.15

shuu_01

No.12 で書き忘れましたが、180 X 90cm の板、15 枚必要と思います

お礼

必要枚数は15枚なのですね。
回答を下さいまして大変ありがたいです。
この度はご親切にありがとうございました。
感謝です！！！

回答No.14

shuu_01

No.6 さんの教えてくださったシェアウェア「板取君2」 でも試してみました

まず　「システム設計」　で

部材の切取順序の設定：総当たり　（低速）
部材の回転方式の設定：総当たり　（低速）

を選ぶと、「計算量が多すぎます」 とアラートが出て、
部材を減らすか、システム設計を変更するよう
言われました

そこで、

部材の切取順序の設定：同一部材は連続して切り取る　（中低速）
部材の回転方式の設定：総当たり　（低速）

を設定して計算すると、１時間以上かかって計算し、
なんと １８枚になってしまいました

僕の最初のトライと偶然にも同じ数字です

今回のデータ量は板前君には大きすぎたようです

お礼

データ量が大きかったようで、設定を限定することになったのですね。
であれば18枚という結果も頷ける気がします。
総当たりにすると全ての組み合わせが何通りあるのか、数学に疎くてあまり良く分からないのですが、仮に全ての数を掛け合わせると700万を超えるようです。
計算量が大きすぎたのでしょうか。
回答ありがとうございました。

回答No.13

shuu_01

No.12 の続きです

お礼

大変わかりやすいです。
回答ありがとうございました。

回答No.12

shuu_01

No.10 が僕の勘違いでないとして、g を 18枚に増やしてみました

回答No.11

shuu_01

No.10 の２枚目の画像です

お礼

ありがとうございます。

回答No.10

shuu_01

No.5 さん、14枚はすごいです！
そこで確認してみましたが、g が本来 18枚 なのですが、15枚しかないのでは？
僕の勘違いでしょうか？
１つだと見にくいので、次の回答と合わせて２枚の画像で貼ります

お礼

大変分かりやすいです。
回答ありがとうございました。

回答No.9

shuu_01

No.6 さんに教えて頂いた　板取君2(いたどりくん2)
シェアウェアでしたので、ダウンロードしてみると、
なんか無限ループに入ってしまいました
今日、帰ったらまたやってみます

お礼

無限ループ回避はプログラミング学習におけるいろはのいだと思っていました・・・
わざわざ試して下さりありがとうございました。