0

長方形の紙は、W*H(幅*高さ)で与えられます。そこから長方形のピースを切り取ることになっています。断片のサイズのリスト ('k' 要素を持つ) が与えられます。ピースのサイズは w*h で与えられます。すべての数値は整数です。

カットは端から端まで行う必要があります。

リストされたサイズのピースがいくつでも存在する可能性があります (ピースなしを含む)。

目的は、できるだけ多くの紙を使用すること、つまり無駄を最小限に抑えることです。

誰でもこの問題にアプローチする方法を教えてもらえますか?

4

1 に答える 1

1

これは典型的なナップザックの問題です。ここでは詳細を割愛しますが、ここでアプローチ方法に関する詳細情報とアイデアを得ることができます

http://en.wikipedia.org/wiki/Knapsack_problem

于 2012-10-30T22:30:51.857 に答える