动态规划:盒子堆叠变化 [英] Dynamic programming: box stacking variation
问题描述
我们有 n 个尺寸为 x、y、z(宽度、高度、深度)的盒子.我们想在另一个中插入最大数量的盒子.
如果内盒 (i) 的大小严格小于外盒 (j) 的大小，您可以将一个盒子放入另一个盒子中:x[i]
We have n boxes whose dimensions are x, y, z (width, height, depth).
We want to insert the largest number of boxes one inside the other.
You can put a box inside the other if the size of the inner box (i) are strictly less than the size of the outer box (j): x[i] < x[j], y[i] < y[j], z[i] < z[j].
The boxes CAN'T be rotated and can be considered in any order.
如何通过动态规划实现目标?
该问题类似于最长递增子序列问题?
按升序/降序对框进行排序是否有意义?
How can I achieve the goal with the dynamic programming?
The issue is similar to the longest increasing subsequence problem?
It can make sense to order boxes in ascending / descending order?
推荐答案
对框进行拓扑排序，将它们排列成图如下: 每个框是图中的一个节点，从节点 A 到节点的每条有向弧B 表示对应的 Box A 持有 Box B.用一个无限大小的框和一个零大小的框来扩充这个结构.
Perform a topological sort on the boxes, arranging them into a graph as follows: Each box is a node in a graph, each directed arc from node A to node B indicates that the corresponding Box A holds Box B. Augment this structure with a box of infinite size and a box a zero size.
作为拓扑排序，这个图将是一个有向无环图.因此，找到最长路径不是 NP-hard，而是可以在 O(V+E) 中解决.两个扩充框之间的最长路径包含问题的答案.
As a topological sort, this graph will be a directed acyclic graph. As such, finding the longest path is not NP-hard, but rather can be solved in O(V+E). The longest path between your two augmenting boxes contains the answer to the problem.
设置排序是 O(V^2)，从排序图中找到解决方案是 O(V+E)，在这种情况下是 O(V^2)，这是您的整体解决方案时间.
Setting up the sort is O(V^2), and finding the solution from the sorted graph is O(V+E) which in this context is O(V^2) which is your overall solution time.
这篇关于动态规划:盒子堆叠变化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
