0

我了解 Box Stacking 问题的动态编程解决方案，它试图找到可以由一组给定的盒子形成的堆栈的最大可能长度，可以在任何方向上旋转，这样下面的盒子总是更小与堆栈中较高的盒子相比，其宽度和长度。

但是，我无法理解为什么每个盒子只需要 3 个方向。根据我的说法，方向的数量应该是 6。也就是说，对于作为高度的三个维度中的每一个，你应该有两种组合。

在线资源显示以下作为创建原始框的三个方向（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}，三个方向将是

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

我知道我额外的三个组合是由于它们之间的长度和宽度交替保持高度相同。因此，尽管我认为 1 2 3 和 1 3 2 不同，但原始算法认为它们是相同的。

但是，我觉得，在这个问题中，h,l,w 和 h,w,l 应该被视为两个独立的方向，因为一个盒子说，l=3,w=4,h=5 可以堆叠在一个盒子上方比如说，l=4,w=5 ,h=6，但不在盒子上方l=5,w=4 ,h=6

4

1 回答 1

0

你说的完全正确，我们可以采用 6 个方向的盒子，但问题是我们可以只用 3 个方向的盒子。

这是因为我们强加了一个规则，即给定一个盒子的高度、宽度和长度，我们将把两个基本尺寸中较小的一个视为宽度。

换句话说，给定一个尺寸为 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 可以堆叠在一个盒子上方比如说，l=4,w=5,h=6，但不在盒子上方 l=5,w=4,h=6

例如，如果有两个盒子

h1,w1,l1 (Box1) 和
h2,w2,l2 (Box2)

我们知道w1<l1（因为我们已经施加了这个限制）所以如果偶然w1>w2我们自动知道l1> w2，因此不需要其他盒子配置（你说应该交换w并被l视为单独的配置）。

想想看，我相信你会明白为什么我们只使用 3 种配置。

于 2015-10-16T12:13:36.073 回答