4

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

この質問は SO ( Box stacking problem ) で尋ねられましたが、「繰り返しなし」の制約はありません。LIS を使用してこれをどのように解決しますか。

私は次の解決策を考案しました。議論できますか

H[j] = max(H[j],max(H[i]|i<j, D[j] < D[i] , W[j]<W[i]+ H[j] -H[j'] )

ここで、 h[j'] は、 j 番目のボックスが H[i] の計算に既に使用されている場合に他なりません。回転が許可されているため、H[j] は j 番目のボックスの幅または深さになります。

4

2 に答える 2

0

この結果はもともと 2D の場合に得られたものですが、最後に説明したように 3D ボックスにも当てはまります。

最適なタワー内のすべてのボックスが、それらの長い次元の EW に整列されているか、または整列されていると便利です。

EW と NS の両方に向けられるいくつかの (ゼロではない) ボックスの数を必要とする最適なタワーを備えたボックスのセットを想定します。一番下のボックスが東西に揃うように、そのようなタワーを回転させます。ここで、NS に位置合わせされた一番下のボックス i を考えてみましょう。明らかに、ボックス i の長さ寸法は、そのサポーター ボックス i-1 の最小寸法よりも小さくなっています。したがって、ボックス i の長さ寸法は、ボックス i-1 の長さ寸法よりも小さくなります。

同様に、ボックス i の短次元はボックス i の長次元よりも小さいため、推移性によって、ボックス i の短次元はボックス i-1 の短次元よりも小さいことがわかります。したがって、ボックス i から上のサブタワー全体を 90 度回転させて、ボックス i を EW に揃えることができます。

タワーを上っていくうちに、すべてのボックスを最適なタワーの東西に並べることができることは明らかです。

したがって、各ボックスには、最適なタワーで可能な「向き」のみがあります。

  • 高さの方向: 最長寸法の垂直方向、2 番目に長い EW 方向。
  • 長さの方向: 最長の寸法 EW、2 番目に長い寸法の垂直。
  • 幅の方向: 最長寸法 EW、2 番目に長い寸法方向 NS。
  • 不在。
于 2013-03-08T19:44:38.817 に答える
-1

提供したリンクでDPソリューションを使用し、各位置にサイズnビットマップを配置することで、「繰り返しなし」の制約を取り除くことができます。

これはあなたの計画された解決策のように聞こえますが、私はあなたの式やコードに完全に従っていません.

各ボックスのインデックスは、その 3 回の回転間で共通であり、ボックスのインデックスのビットマップ内のビットは、同じボックスの次の回転が処理されないように設定されます。

for i = 1:n  
  Box b = inputi  
  (h3i  , w3i  , d3i  ) = getRotation1(b)  
  (h3i+1, w3i+1, d3i+1) = getRotation2(b)  
  (h3i+2, w3i+2, d3i+2) = getRotation3(b)  
  index3i = index3i+1 = index3i+2 = i

// sort the 4 fields simultaneously (hi, wi, di, indexi all belong to the same box)
// (easy to do in OOP by storing these 4 in the same object)
sortByAreaDesc(h, w, d, index)

H[0] = 0
bitmap0 = {false}

for j = 1:3n
  H[j] = maxi < j, wi > wj, di > dj { if (bitmapj[ indexi ]) 0 else H[i] } + hj  
  bitmapj = bitmapi from max
  bitmapj[ indexi from max ] = true

return maxj H[j]

O(n 2 ) の時間とスペースが必要です。

于 2013-03-08T20:55:04.963 に答える