この問題の適切な解決策を見つけるのを手伝ってください。
3 次元の n 個のボックスがあります。それらを方向付けることができ、最大の高さになるようにそれらを別の上に置きたい. 2 つの寸法 (幅と長さ) が下のボックスの寸法よりも小さい場合、ボックスを別のボックスの上に置くことができます。
たとえば、w*D*h の 3 つの次元があり、(h*d,d*h,w*d,d*W,h*w,w*h) で表示できます。グラフ理論。この問題では、(2*3) を (2*4) の上に配置することはできません。これは、幅が同じであるためです。したがって、2 次元はボックスよりも小さくする必要があります。
編集：ボックスがすべての軸を中心に回転できない場合にのみ機能します。
質問を正しく理解すれば、動的計画法で解決できます。最大スタックの高さを見つける簡単なアルゴリズムは次のとおりです。
ボックスB_iの場合、w_i <= d_iになるように、すべてのボックスを回転させることから始めます。これには時間O（n）がかかります。
次に、下部の領域w_i * d_iに従ってボックスを並べ替え、インデックスにこれを表示させます。これには時間O（n log n）がかかります。
これで、B_iはi <jの場合にのみB_jに配置できますが、i <jは、B_iがB_jに配置できることを意味するものではありません。
B_jが一番上にある最大のスタックは次のいずれかです
これで、最大スタックの高さを計算するための再帰式を作成できます
H（j）= max（h_j、max（H（i）| i <j、d_i <d_j、w_i <w_j）+ h_j）
max（H（j）、i <= j <= n）を計算することにより、最大スタックの高さを取得します。
実際のスタックが必要な場合は、H関数にいくつかの情報を添付して、インデックスを覚えておくことができます。
更新されました（正しいですか？しかし、おそらく最も効率的ではありません）：
各ボックスは 3 つの頂点になります (これらの頂点を関連付けると呼びます)。重み付けされた DAG を取得します。ここで説明されているアルゴリズムを変更します (いくつかの頂点が関連しているという事実を無視して) トポロジ的に並べ替え、アルゴリズムに従いますが、整数の配列ではなく、各頂点につながるパスのリストを保持します。次に、新しい頂点 (wiki alg の「w」) へのパスを追加するときに、w に関連する頂点を含む v へのパスをドロップして、そこにつながるパスのリストを作成します。元のアルゴリズムとは異なり、これは指数関数的です。
元の間違った答え (コメントを参照):
各ボックスは、3 つのサーフェス サイズに対して 3 つのノードになります。次に、各面を小さいサイズのすべての面に接続する有向グラフを作成します。エッジがつながるノードの 3 番目の次元 (つまり、高さ) と等しくなるように、各エッジに価格を割り当てます。これは、DAG で最長パスの問題を見つける問題です。