0

ボックス スタッキング問題の動的計画法の解決策を理解しています。これは、下のボックスが常に小さくなるように、任意の方向に回転できるボックスの特定のセットによって形成できるスタックの最大長を見つけようとするものです。スタックでより高いボックスと比較して、幅と長さが異なります。

ただし、すべてのボックスに 3 つの方向のみが必要な理由を理解できませんでした。私によると、方向の数は 6 である必要があります。つまり、高さと見なされる 3 つの次元のそれぞれについて、2 つの組み合わせが必要です。

オンラインリソースでは、元のボックスの 3 つの方向 (2 回転) を作成する方法として次のように示されています。

/* Create an array of all rotations of given boxes
      For example, for a box {1, 2, 3}, we consider three
      instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */
   Box rot[3*n];
   int index = 0;
   for (int i = 0; i < n; i++)
   {
      // Copy the original box
      rot[index] = arr[i];
      index++;

      // First rotation of box
      rot[index].h = arr[i].w;
      rot[index].d = max(arr[i].h, arr[i].d);
      rot[index].w = min(arr[i].h, arr[i].d);
      index++;

      // Second rotation of box
      rot[index].h = arr[i].d;
      rot[index].d = max(arr[i].h, arr[i].w);
      rot[index].w = min(arr[i].h, arr[i].w);
      index++;
   }

たとえば、ボックス {1, 2, 3} の場合、3 つの方向は次のようになります。

1 2 3
2 1 3
3 1 2

しかし、私によると、オリエンテーションは

1 2 3
1 3 2

2 1 3
2 3 1

3 1 2
3 2 1

余分な 3 つの組み合わせは、高さを同じに保ちながら長さと幅を交互に変えているためだと理解しています。したがって、私は 1 2 3 と 1 3 2 を異なるものと見なしますが、元のアルゴリズムはそれらを同じと見なします。

ただし、この問題では、h、l、w と h、w、l は、l=3、w=4、h=5 というボックスをボックスの上に積み重ねることができるため、2 つの別々の向きとして扱う必要があると思います。l=4,w=5 ,h=6 としますが、ボックスの上ではありませんl =5,w=4 ,h=6

4

1 に答える 1

0

あなたが言ったことは完全に正しいですが、ボックスの 6 つの向きを取ることができますが、問題は、ボックスの 3 つの向きだけで間に合わせることができるということです。

これは、ボックスの高さ、幅、および長さが与えられた場合、2 つの基本寸法のうち小さい方を幅として扱うという規則を課すためです。

言い換えると、x > y > z の寸法のボックスが与えられた場合、方向を考慮します。

h=x, l=y, w=z
h=y, l=x, w=z
h=z, l=x, w=y

ただし、次のような向きではありません。

h=x, l=z, w=y
h=y, l=z, w=x
h=z, l=y, w=x

これは単にボックスの表現を単純化するためです。
あなたが指定したリンクでも、彼らは書いています
for simplicity of solution, always keep w<=d：

struct Box
{
  // h –&gt; height, w –&gt; width, d –&gt; depth
  int h, w, d;  // for simplicity of solution, always keep w <= d
};

この制約をデータに課したので、元の問題が解決されたことがわかります。

ただし、この問題では、h、l、w と h、w、l は、l=3、w=4、h=5 というボックスをボックスの上に積み重ねることができるため、2 つの別々の向きとして扱う必要があると思います。 l=4,w=5,h=6 としますが、ボックスの上ではありません l=5,w=4,h=6

例えば、箱が2つあった場合

h1,w1,l1 (Box1) および
h2,w2,l2 (Box2)

私たちはw1<l1（その制限を課したため）知っているので、偶然w1>w2にも自動的l1> w2に知っているので、他のボックス構成（あなたが言った場所を交換して別の構成wとl見なす必要がある場所）は必要ありません。

考えてみてください。3 つの構成のみを使用する理由が理解できると思います。

于 2015-10-16T12:13:36.073 に答える