板取り問題

質問

学校で以下のような問題が出題されました。

長さが35, 60, 100, 150の板には, それぞれ500, 700, 450, 200枚以上の需要があり, これらを長さ1000の板から取り出したい. このとき, 使用する長さ1000の板の総枚数が最小になるためには, どのような取り出しパターンで, 各板が何枚必要か。

いま一つ理解できなかったので、解説していただきたいのですが。
よろしくお願いします。

回答No.5

su_zu · ベストアンサー

板ということなので、二次元の問題のようにも思えますが、幅の記載がないので
一次元の割付問題と考えて、参考URLで配布されているソフトを使って求めてみたら

35枚：　150 x 2、 100 x 2、 60 x 6、 35 x 4　　
30枚：　150 x 2、 100 x 1、 60 x 7、 35 x 5
70枚：　150 x 1、 100 x 5、 60 x 4、 35 x 3

の、合計135枚必要となりました。

参考URL：

http://supermab.com

お礼

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

回答No.4

su_zu

板ということなので、二次元の問題のようにも思えますが、幅の記載がないので
一次元の割付問題と考えて、参考URLで配布されているソフトを使って求めてみたら

35枚：　150 x 2 100 x 2 60 x 6 35 x 4　　
30枚：　150 x 2 100 x 1 60 x 7 35 x 5
70枚：　150 x 1 100 x 5 60 x 4 35 x 3

の、合計135枚必要となりました。

参考URL：

http://supermab.com

回答No.3

tmpname

つまり例えば
＊「長さ35の板を20枚、長さ100の板を3枚」切り出すという
　パターンが10枚
＊「長さ150の板を6枚、長さ100の板を1枚」切り出すという
　パターンが20枚
＊「長さ60の板を5枚、長さ100の板を7枚」切り出すという
　パターンが30枚
....
....
といった感じで合計長さ35の板を最低500枚（残り略）作り出す時、
各パターンとそのパターンの板が何枚あるかを答えよ、と
言う事です
＊上の例はあくまで「例えば」です

お礼

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

回答No.2

tmpname

要は例えば長さ1000の板から長さ60の板だけを切り出そうと
すると、16枚切り出せますが40だけ余りが出ます。
この残り40の板からは例えば長さ35の板を切り出せますが、
それでも5だけ余ります。この残り5の板からは35, 60, 100,
150どの長さの板も切り出せず、無駄になります。

これを長さ1000の板から例えば長さ35の板を20枚、
100の板を3枚切り出せば、無駄無く長さ1000の板を使うことが
出来ます。同様に例えば長さ1000の板から長さ60の板を
15枚、長さ100の板を1枚切り出せば無駄無く長さ
1000の板を使いきることが出来ます。

つまり、複数の長さ1000の板から、なるべく無駄が無いように
切り出す板の種類とその枚数を組み合わせて板を切り出して
行く時、長さ1000の板は結局何枚必要か？という問題です。

( 35.*500 + 60.*700 + 100.*450 + 150*200.) / 1000 = 134.5で
あることから、どんなに無駄が無いように長さ1000の板を
使っても長さ1000の板は135枚必要な事が分かりますが、本当に
135枚でうまく切り出せるか？という事です。

で私が試すと135枚で実際うまく行きましたので色々試して
見てください。

お礼

回答ありがとうございます。
つまり、長さ1000の板の総枚数は１３５枚となり、各板の必要枚数は何通りも存在するということでしょうか。

回答No.1

Tacosan

うん, 確かに「今一つ理解できない」問題だね.
とりあえず, この問題を出した人に聞いた方がいいんじゃないかな.