板取り問題

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

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

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

No.5 ベストアンサー 回答者： su_zu 回答日時： 2010/12/20 22:35

板ということなので、二次元の問題のようにも思えますが、幅の記載がないので

一次元の割付問題と考えて、参考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

この回答へのお礼

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

お礼日時：2010/12/21 00:20

No.4 回答者： su_zu 回答日時： 2010/12/20 22:32

板ということなので、二次元の問題のようにも思えますが、幅の記載がないので

一次元の割付問題と考えて、参考URLで配布されているソフトを使って求めてみたら

35枚：　150 x 2100 x 260 x 635 x 4　　
30枚：　150 x 2100 x 160 x 735 x 5
70枚：　150 x 1100 x 560 x 435 x 3

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

参考URL：http://supermab.com

No.3 回答者： tmpname 回答日時： 2010/12/20 20:35

つまり例えば

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

この回答へのお礼

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

お礼日時：2010/12/21 00:22

No.2 回答者： tmpname 回答日時： 2010/12/20 20:08

要は例えば長さ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の板の総枚数は１３５枚となり、各板の必要枚数は何通りも存在するということでしょうか。

お礼日時：2010/12/20 20:18

No.1 回答者： Tacosan 回答日時： 2010/12/20 18:50

うん, 確かに「今一つ理解できない」問題だね.

とりあえず, この問題を出した人に聞いた方がいいんじゃないかな.