如何获得堆放箱子的最大高度？

Question

有一组 20 个框，参数为 {height, length, width}。如果 {length_of_first, width_of_first} 小于或等于 {length_of_second, width_of_second}，则一个盒子可以堆叠在另一个盒子上，即

length_of_first <= length_of_second && width_of_first <= width_of_second。盒子可以在任何一侧旋转

BoxSizes rotateRight(const BoxSizes& box) {
    BoxSizes box_sizes(box);

    int height = box_sizes.height;
    int width = box_sizes.width;
    int length = box_sizes.length;

    box_sizes.length = width;
    box_sizes.height = length;
    box_sizes.width = height;

    return box_sizes;
}

BoxSizes rotateOnward(const BoxSizes& box) {
    BoxSizes box_sizes(box);

    int height = box_sizes.height;
    int width = box_sizes.width;
    int length = box_sizes.length;

    box_sizes.length = height;
    box_sizes.height = length;
    box_sizes.width = width;

    return box_sizes;
}

主要目标是获得最高的箱子堆。不强制使用所有盒子，但一个盒子必须只使用一次！例子。给定两个盒子：

{27, 24, 35},
{76, 36, 3}

我可以堆两个箱子，但最好不要堆，拿第二个箱子旋转它得到76。

我应该用什么方法来解决这个问题因为我不能使用bruteforce因为我需要考虑每个盒子的3旋转所以我需要运行 (3 + 1) ^ 20 例（+1 因为一个盒子可能用不到）

Answer 1

我的建议是采用一种混合方法，使用动态规划生成堆高上限，然后使用 A* 搜索来找到解决方案。

首先，让我们构建一个具有 60 个节点的图表，表示刚刚将 20 个盒子中的一个放在 3 个方向中的每个方向上。为空堆再添加一个。

如果B可以堆在A上，你的箭就是A -> B。“可以堆”意味着它符合你的堆放规则，还有以下额外规则。如果长度和宽度匹配，则只能将较短的堆放在较长的上面。如果框尺寸相同，则执行任意顺序。

这些限制的原因是，如果有一个有效答案不遵循这些附加规则，您可以重新排列框以找到符合这些规则的相同高度之一。所以我们只需要寻找遵循这些规则的安排。有了这些循环，我们的图中就没有循环了。

接下来，通过简单的递归图搜索，对于每个有方向的框，我们可以找到可以在其上堆放的最高堆，忽略重复规则。记录下那61个高度。

这些高度高估了您可以建造多高的桩。但我们并没有试图强制执行关于永远不重复使用盒子的规则。让我们用 A* 搜索来解决这个问题。

我们首先需要一个 Priority Queue 那个 returns 最大的优先级。（最大堆会做得很好。）这样，我们的搜索将按照以下伪代码进行。

queue.add((max height on empty ground, 0, empty path))
while True: # loop condition terminates at end.
    (priority, height, path) = queue.pop()
    if priority = height:
        EXIT HERE, HEIGHT IS ANSWER AND PATH IS OPTIMAL PILING
    else:
        queue.add((height, height, path))
        for oriented box that can pile on last in path: # in graph above
            if box not in path:
                new_height = height + height of box
                queue.add((
                    new_height + max_height on orientation,
                    new_height,
                    path with orientation added))

这将做的是从一条空路径开始，将每个方向放入队列，然后贪婪地探索尝试你第一次找到的最高桩，每当它遇到重复的盒子标准时回溯。我们得到的优先级永远是最高堆的高度的上限。高度是到目前为止这堆的高度。这就是为什么当我们找到一个实际高度与优先级匹配的堆时，这就是最佳答案。

Answer 2

正如“btilly”先生所说，我们应该根据方框的所有可能旋转创建一个图表。

每个节点代表一个旋转的（或原始形状）框。

只有当第二个盒子可以堆在第一个盒子上时，节点之间的边才能存在。

那么，让我们介绍一个描述盒子形状的结构：

struct BoxSizes {
    int length{};
    int width{};
    int height{};
    int type{-1};
    int num_of_box{};

    BoxSizes(const BoxSizes&) = default;
    BoxSizes(const std::vector<int>& box, int type, int num_of_box) : length(box[0]), width(box[1]), height(box[2]), type(type), num_of_box(num_of_box) {}
    /*Some helpful methods*/

我们给出这样的盒子形状：

std::vector<std::vector<int>> box_sizes = {
            {269, 152, 375},
            {45, 8, 259},
            {37, 113, 98},
            {685, 40, 35}
};

让我们创建盒子的所有旋转：

std::vector<BoxSizes> all_rotated_box;

for (const auto& box_as_vector : box_sizes) {
     /*Don't pay attention on type and count*/
     const auto& box = BoxSizes(box_as_vector, type++, count);
     count += 3;
     all_rotated_box.emplace_back(box);
     all_rotated_box.emplace_back(rotateRight(box));
     all_rotated_box.emplace_back(rotateOnward(box));
}

/*Let's sort them!*/
std::sort(all_rotated_box.begin(), all_rotated_box.end());

那么，我们来介绍一个结构Node

struct Node {
        int x, y, z;
        int type;
        Node() = default;
        Node(int _x, int _y, int _z, int type) : x(_x), y(_y), z(_z), type(type) {}
        bool operator==(Node a) {
            return (x == a.x) && (y == a.y);
        }
};

std::vector<Node> nodes;

/*From vector of boxes to vector of nodes*/
std::transform(all_rotated_box.begin(), all_rotated_box.end(), std::back_inserter(nodes),
                   [](const auto& box) { return  Node(box.length, box.width, box.height, box.type); });

让我们创建一个图表：

std::vector<std::vector<int>> Graph(nodes.size(), std::vector<int>(nodes.size(), 0));

    for (int i = 0; i < nodes.size(); i++) {
        auto x = nodes[i].x;
        auto y = nodes[i].y;
        auto type = nodes[i].type;

        for (int j = 0; j < nodes.size(); j++) {
            auto x_ = nodes[j].x;
            auto y_ = nodes[j].y;
            auto type_ = nodes[j].type;

            if(i == j) {
                Graph[i][j] = nodes[i].z;
            }

            if(type == type_ || (x == x_ && y == y_))
                continue;

            if((x < x_ || x <= x_) && (y < y_ || y <= y_) ||
               (x < y_ || x <= y_) && (y < x_ || y <= x_)) {
                Graph[i][j] = std::abs( nodes[j].z);
            }

        }
    }

所以，主循环是：

for(auto j = 0; j < nodes.size(); j++) {
        std::deque<int> q;

        q.push_back(j);

        std::vector<int> heighest(nodes.size(), 0);
        heighest[j] = Graph[j][j];

        while (!q.empty()) {
            std::vector<int> adjacent_nodes;

            auto curr{q.front()};
            q.pop_front();

            for (int i = 0; i < Graph[0].size(); i++) {
                if (Graph[curr][i] > 0 && i != curr) {
                    adjacent_nodes.push_back(i);
                }
            }

            for (auto node : adjacent_nodes) {
                heighest[node] = std::max(heighest[node], heighest[curr] + Graph[curr][node]);
                q.push_back(node);
            }
        }

        the_heighest = std::max(the_heighest, *std::max_element(heighest.begin(), heighest.end()));
    }

你可以在这里查看https://github.com/Ayrtat/codeforces/blob/master/BoxRight.cpp

如何获得堆放箱子的最大高度？

How to get maximum height of piled boxes?

algorithm

dynamic-programming