特定の量の長方形（定義された幅がランダムな高さを持つ）を別の長方形（定義された高さと挿入する長方形と同じ定義された幅を持つ）に挿入するという要件があります。ここでの目標は、挿入された長方形がターゲットの長方形を可能な限り埋めることです。
例えば：
黒にできるだけ多くの長方形を入れる必要はありません。目標は、黒の長方形をできるだけ完全に塗りつぶすことです。
実際には、多くの「黒い」長方形と何千もの「赤い」があります。私は計算するための効果的なアルゴリズムを探しています。これをECMA-/Javascriptで実装する必要があるため、すべてのプラットフォームの中で実際に最速ではありません。
リチャード・E・コルフの「最適な長方形のパッキング」や「ビンのパッキングの問題」のようないくつかのアルゴを調べましたが、この特定の問題についてそれらを実際に翻訳することはできませんでした。
誰かが私に方法/アルゴリズムを勧めてもらえますか？
赤と黒の三角形はどちらも幅が定義されているため、問題をいわば数直線に減らすことができます。基本的に、赤いものを横向きにひっくり返すと、無駄なスペースができてしまう可能性が高く、「通常のフィッティング」方法で置くよりもはるかに多くのスペースが無駄になります。
したがって、これを念頭に置いて、容量が黒い長方形の高さであり、赤い三角形の「重量」がそれらの高さである従来のナップザックの問題に正確に問題を減らすことができます. 幅は問題から完全に抽象化できます。
もう 1 つの利点 (xvatar で指摘されているように) は、候補の値密度がすべて等しいことです。つまり、従来のナップザックの問題に見られる「ブリック リング」の問題はありません。ナップザックに詰めるブロックとリングのどちらを選ぶかを考えると、リングは明らかな候補です。この場合、それらはすべて同じであるため、明確な候補はありません。
大きなブロックは簡単な候補のように思えますが、この貪欲なアプローチは成功しません。残りのスペースが 5 ユニットで、4、3、2 のレンガがあるシナリオを考えてみましょう。貪欲なソリューションを使用する場合は、4 を追加して、1 つの空きスペースを残します。代わりに 3 と 2 を使用した場合、1 の空きスペースが残っていないことになります。
また、どの長方形が入るかを特定したら、それらがどの順序で入るかは問題ではないことに注意してください。