箱堆放问题 [英] Box stacking problem

问题描述

我发现在很多地方这个著名的DP问题，但我不知道如何解决。

I found this famous dp problem in many places, but I can not figure out how to solve.

正在给定一组N种   矩形的3-D盒，其中第i ^第   箱具有高度h（i）中，宽度w（i）和   深度d（i）（由所有实数）。您   要创建一堆箱子哪些   是一样高的可能，但你可以   只有堆盒子上的另一个盒子顶部   如果的2-D基的尺寸   下面的对话框中分别严格较大   比的二维碱   高框。当然，你可以旋转   一个对话框，以便任何一方职能   它的基础。另外，也可使用   相同类型的多个实例   框。

You are given a set of n types of rectangular 3-D boxes, where the i^th box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. It is also allowable to use multiple instances of the same type of box.

这个问题似乎过于复杂，我要弄清楚的步骤。因为它是3D的，我得到三个序列的高度，宽度和深度。但是，因为它是可以更换3维的问题变得更加复杂，我。所以，请人介绍的步骤来解决问题时，有没有交换，然后如何交换的时候做。我累了这个问题。所以，请请有人解释该解决方案简单的方法。

This problem seems too complicated for me to figure out the steps. As it is 3D, I get three sequence of height, width and depth. But as it is possible to exchange 3 dimension the problem becomes more complicated for me. So please someone explain the steps to solve the problem when there is no swapping and then how to do it when swapping. I became tired about the problem. So please, please someone explain the solution easy way.

推荐答案

我觉得你可以在此使用动态规划的最长递增子的算法解决：<一href="http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence">http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

I think you can solve this using the dynamic programming longest increasing subsequence algorithm: http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence

占轮换是很容易的：每塔所有你要检查的是，如果你使用它的高度为基准的长度和宽度与高度，会发生什么，如果你在自然的方式使用它会发生什么。例如：

Accounting for the rotations is easy enough: for every tower all you have to check is what happens if you use its height as the length of the base and its width as the height and what happens if you use it in the natural way. For example:

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

变为像（是的，我知道它看起来像什么也没有要，只要按照符号）：

Becomes something like (yeah, I know it looks nothing like it should, just follow the notations):

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

因此​​，对于每个块，你实际上有3个街区重新presenting其可能的旋转。根据此调整块阵列，然后排序下降基地面积，只是应用DP LIS算法来获得的最大高度。

So for each block you actually have 3 blocks representing its possible rotations. Adjust your blocks array according to this, then sort by decreasing base area and just apply the DP LIS algorithm to the get the maximum height.

在适应复发是：D [i] =最大高度，我们可以，如果最后的塔一定是我获得

The adapted recurrence is: D[i] = maximum height we can obtain if the last tower must be 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 /

See a video explaning this here: http://people.csail.mit.edu/bdean/6.046/dp/

这篇关于箱堆放问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！