algorithm - 効果的な木板切断アルゴリズム

Question

無駄を最小限に抑えて木の板を切断するアルゴリズムを考え出す必要があります。切断機は直線で切断します。90°回転して続行するなど、途中で停止することはできません。

例:
寸法が 280cm x 207cm の木製ボードがあり、切断プロセス後の廃棄物を最小限に抑える必要があります。

次のテーブルの幅と長さのセットがあります。

幅
140
140
140
197
197
30,5
30,5

長さ
33
33
33
33
33
33
33

長さが常に同じなので、「Greedyアルゴリズム」を使用することを考えています。何か案は？

Answer 1

これは、NP 困難な 2D ビン パッキングの変形です。それに対する一般的な近似は、ピースを幅でソートしてから、まだ十分な残りの最小のボードからピースを切り出し始めることです. これとさらに複雑なアルゴリズムについて詳しくは、http://cgi.csc.liv.ac.uk/~epa/surveyhtml.htmlをご覧ください。