algorithm - 長方形フィールド内の可変サイズの長方形の効率的な配置

Question

これは、ナップザックの問題のバージョンのように思えます。さまざまなサイズの長方形のリストがあり、同じようなサイズを重ねたりグループ化したりせずに、フィールド内に配置したいと考えています。

ナップザックの方向に目を向け始めるのは正しいでしょうか?

ありがとう。

Answer 1

はい、それはナップザックの問題と同じ種類の問題です - 1 つだけでなく 2 つの次元を処理する必要があるため、より困難です - しかし、ナップザックの問題を探すことで、あなたは正しい道を進んでいます。

Answer 2

ナップザックの問題は、フィールドと長方形を固定幅 (任意の長方形の最小の長さよりも小さい幅) にすることで解決できるため、少なくともナップザックと同じくらい難しいです。