一枚の板から何枚取れるか？

「縦H×横Wの板があります。
　この板から縦h×横wのいたが何枚とれますか？」

という問題を解きたいのですが、お決まりの解法
というのがあるのでしょうか。

縦方向で、縦横それぞれの商の小さいほうを取り、
横向きで同じく小さいほうの値をとって、それら
のうち大きいほうを解とする　というやり方しか
思い浮かびません。

よろしくお願いします。

No.2 ベストアンサー 回答者： sunasearch 回答日時： 2005/04/22 23:16

この問題は、組合せ最適化問題に帰着されると思いますので、

試行錯誤的に解を見つける必要があると思います。

まず、もとの板の縦方向に着目して、
縦方向にa枚、横方向にb枚板を切り取ると考え、
ah+bw <= Hとなるa,bのすべての組合せと、
斜め方向に真ん中に板が入る可能性を考えます。

今度はもとの板の横方向に着目して、同様に、
ch+dw <= Wとなるc,dのすべての組合せと、
斜め方向に真ん中に板が入る可能性を考えます。

これらすべての可能性の中で、
もっとも多くなる数を探す必要があるかと思います。

この回答へのお礼

sunasearch 様、ありがとうございます。

斜め　というのがいやらしいですね。

公式に放り込んでおしまい！
といったものでないのですね・・・

これをExcelでやれ　といわれている
のですが、ソルバーなんかを使うので
しょうか（使ったことないケド）

お礼日時：2005/04/25 15:30

No.1 回答者： noname#10563 回答日時： 2005/04/22 19:46

だめだと思います。

理由↓

２９×２９の板から１０×１０の板は何枚取れるか？
単純計算なら４枚ですが，現実的には少なくとも５枚取れます。
４隅から１０×１０の板を４枚取り，十文字の残った板の
真ん中部分から１０×１０の板がもう一枚取れます。
斜めにすれば・・・・

難しいですね＾＾；

この回答へのお礼

なるほど！
斜めは気が付きませんでした・・・

簡単に考えすぎていたかも・・・

お礼日時：2005/04/25 15:26