n個の長方形のn個の長方形をn個の大きな長方形に合わせる

Question

n個の長方形と長方形のn個の長方形（小さいもの）があり、n個の長さと幅のn個の長方形があります。要するに、フィッティングされる矩形のリストと、これらの矩形がフィッティングされる矩形のリストがあります。

私はさまざまなパッケージフィッティングアルゴリズムについて勉強していますが、私はさまざまな質問が同じことを求められていることを知っていますが、このタイプの問題で私を助けることはできません。

私の質問は、どの大きな矩形を最初に選択するのか、小さな矩形をすべて重なり合わないようにする方法と、小さな矩形を大きなものに合わせるまで最小消耗領域を満たす方法です。すべての小さな四角形がフィットしているときに大きな四角形が塗りつぶされていない場合は、問題ありません。

どこから始めたらいいですか？質問があまり明確でない場合は、私に知らせてください。私の目的は、同じ問題のアルゴリズムを書くことです。

Answer 1

部分的に質問に答えるために、問題はPartitionという問題がサブ問題として含まれているため、NP-hardです。