algorithm - 長方形のボックスをより大きな長方形のボックスに配置する

Question

サイズの異なる特定の長方形のボックスと、より大きな長方形のボックスがあります。より大きなボックスに可能な限り異なるカテゴリのボックスを最大数収める必要があります。いずれの場合も、各カテゴリの特定の最小数のボックスを収容する必要があります。基本的に、制約最適化問題で解決する必要があります。どうすればこれを進めることができますか?

Answer 1

残念ながら、この問題に対する多項式時間アルゴリズムはありません。つまり、NP 困難です。

ということで検索してみる。ボックスを大きい方から小さい方へと並べ替えると役立つ場合があります (領域ごとまたは片側ごと、検索方法によってどちらが優れているかはわかりません)。

速度が許容できない場合は、partical greedy を試して、かなり良い解決策を見つけてください。