31

この有名な dp 問題を多くの場所で見つけましたが、解決方法がわかりません。

n 種類の長方形の 3-D ボックスのセットが与えられます。ここで、i^ 番目のボックスは高さ h(i)、幅 w(i)、深さ d(i) (すべて実数) です。できるだけ高さのあるボックスのスタックを作成したいのですが、ボックスを別のボックスの上にスタックできるのは、下のボックスの 2 次元ベースの寸法が 2 次元ベースの寸法より厳密に大きい場合だけです。ハイボックスのDベース。もちろん、ボックスを回転させて、任意の側面がベースとして機能するようにすることもできます。同じタイプのボックスの複数のインスタンスを使用することもできます。

この問題は複雑すぎて、手順を理解できません。3Dなので、高さ、幅、奥行きの3つのシーケンスを取得します。しかし、3次元を交換することが可能であるため、問題は私にとってより複雑になります. スワッピングがない場合の問題を解決する手順と、スワッピング時にそれを行う方法を誰かが説明してください。私はその問題に疲れました。ですから、誰かが解決策を簡単に説明してください。

4

5 に答える 5

26

動的プログラミングの最長増加サブシーケンスアルゴリズムを使用してこれを解決できると思います: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

回転を説明するのは簡単です。すべてのタワーについて、その高さをベースの長さ、幅を高さとして使用するとどうなるか、自然な方法で使用するとどうなるかを確認する必要があります。例えば：

=============
=           =
=           =
=           = L
=     H     =
=           =
=           =
=============   
      W

次のようになります (ええ、私はそれが本来のように見えないことを知っています。表記に従ってください):

==================
=                =
=                =  
=       W        = L
=                =
=                =
==================
        H

したがって、ブロックごとに、実際には可能な回転を表す 3 つのブロックがあります。これに従ってブロック配列を調整し、ベース領域を減らして並べ替え、DP LIS アルゴリズムを適用して最大高さを取得します。

D[i] = 最後の塔が i でなければならない場合に取得できる最大の高さ。

D[1] = h(1);
D[i] = h(i) + max(D[j] | j < i, we can put block i on top of block j)

Answer is the max element of D.

ここでこれを説明するビデオを参照してください: http://people.csail.mit.edu/bdean/6.046/dp/

于 2010-02-24T21:28:02.407 に答える
6

スタックは、x、y、zトリプレット（x、yは2D平面、zは高さ）のシーケンスと見なすことができます。ここで、x（i）> x（i + 1）およびy（i）> y（ i + 1）。目標は、利用可能なトリプレットのセットからトリプレットを選択するzの合計を最大化することです。各トリプレットは特定の方向のボックスの1つのタイプです。制約x>yを適用しても、解空間が減少しないことは非常に簡単にわかります。したがって、各ボックスは、w、h、dのそれぞれをz座標として持つ3つのトリプレットを生成します。

トリプレットを、x、y制約が満たされたときに、長さzのエッジが2つのトリプレットの間に存在する有向非巡回グラフと見なす場合、問題は、そのグラフを通る最長のパスを見つけることです。

于 2010-02-24T21:29:52.900 に答える
3

まず、この問題を 2 次元で解いてみましょう。

X と Y を持つ長方形があり、質問は似ているとします (最も高い塔ですが、今回は 1 つの底辺の寸法だけを気にする必要があります)。
まず、コレクション全体を調べて、正方形 (X(1)=X(2) && Y(1)=Y(2)) を除いて、90 度回転 (X と Y を交換) して各長方形を複製します。 . これは、考えられるすべてのバリエーションを表しています。
次に、それらを X 側で最大から最小の順に並べ替えます。X 値が重複している場合は、Y 値が小さい方を削除します。

3-D シナリオにも同じ原則が適用されますが、コレクションのサイズを 6 (W、H、D のすべての可能なバリエーション) で乗算するのではなく、2 で乗算するだけではなく、幅が小さいすべてのバリエーションを却下することでこれを行います。深さより (つまり、各 i について、W(i)>=D(i))、高さが 3 つの次元の最高でも最低でもないバリエーションを却下します (他の 2 つのバリエーションが 1 つずつ進む可能性があるため)他のトップとこれは参加できません）。繰り返しますが、重複も無視します (W(1)=W(2) && H(1)=H(2) && D(1)=D(2))。
次に、幅で並べ替える必要がありますが、今回は同じ幅のバリエーションを捨てないでください (タワーに収まる場合とそうでない場合があるため)、上記の @IVlad で説明されている LIS アルゴリズムを使用できます。

D[1] = h(1);
D[i] = h(i) + max(D[j] | j <= i and we can put tower i on tower j) or simply h(i) if no such D[j] exists.

トリックは、幅が 2 つの中で最も長いことを知っているため、最初の要素が後の要素の上に収まらないことがわかっていることです。

于 2010-02-24T21:56:00.503 に答える
0

ツリー (またはある種のツリー構造) を作成し、深さ検索で解析して、個々の垂直方向の「高さ」(回転に依存) 値から最大高さを計算することをお勧めします。

これ（これが基本的なアプローチだと思います）。

詳細以上の詳細:

ツリーのルートは、立方体が収まる床である必要があります。そこから、可能な次のボックス (現在のボックスの上に特定の回転で配置できるボックス) の子ノードを作成するだけです。各ボックスと回転に対して再帰的にそれを行います。

ツリーが構築されたら、それを調べて、床からツリーの葉までのタワーの高さの合計を計算します。

于 2010-02-24T21:16:03.183 に答える
0

この問題の解決策は、3 つのステップで構成されます。

  1. 各ボックスの次元を並べ替えて、任意の 2 つのボックスを比較すると、対応する次元を比較することになります。
  2. ボックスのシーケンスを辞書順に並べ替えて、各ボックスの左側のボックスが適合するボックスになるようにします。
  3. 最長増加部分列問題のO(n^2)アルゴリズムを適用します。

3 番目のステップは最もコストがかかり、ソリューションの複雑さを に上げO(n^2)ます。アプローチの完全な説明、各ステップが答えを見つけるのにどのように役立つか、完全なコードを読みたい場合は、私が問題について書いたブログ投稿をご覧ください。

于 2016-04-09T18:30:12.927 に答える