dポイントプレゼントキャンペーン実施中!

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

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

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

よろしくお願いします。

A 回答 (2件)

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


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

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

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

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

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

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

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

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

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

だめだと思います。


理由↓

29×29の板から10×10の板は何枚取れるか?
単純計算なら4枚ですが,現実的には少なくとも5枚取れます。
4隅から10×10の板を4枚取り,十文字の残った板の
真ん中部分から10×10の板がもう一枚取れます。
斜めにすれば・・・・

難しいですね^^;
    • good
    • 0
この回答へのお礼

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

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

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

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!