c++ - 按给定顺序堆叠箱子的最高塔

Question

给定 N 个盒子。我怎样才能找到按照给定顺序用它们制作的最高塔？ (给定的顺序意味着第一个盒子必须在塔的底部，依此类推)。 所有盒子都必须用于制作有效的塔。

可以在任何轴上旋转盒子，使其 6 个面中的任何一个与地面平行，但是该面的周长必须完全限制在其下方盒子的上表面周长内.在第一个盒子的情况下，可以选择任何面，因为地面足够大。

为了解决这个问题，我尝试了以下方法:
- 首先，代码为每个矩形生成旋转(只是尺寸的排列)
- 其次为每个盒子和每个可能的旋转构造一个动态规划解决方案
- 最后搜索最高的塔(在 dp 表中)

但是我的算法在未知的测试用例中给出了错误的答案。有什么问题吗？动态规划是解决这个问题的最佳方法？

这是我的代码:

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cstring>

struct rectangle{
    int coords[3];
    rectangle(){ coords[0] = coords[1] = coords[2] = 0; }
    rectangle(int a, int b, int c){coords[0] = a; coords[1] = b; coords[2] = c; }
};

bool canStack(rectangle &current_rectangle, rectangle &last_rectangle){
    for (int i = 0; i < 2; ++i)
        if(current_rectangle.coords[i] > last_rectangle.coords[i])
            return false;
    return true;
}

//six is the number of rotations for each rectangle
int dp(std::vector< std::vector<rectangle>  > &v){
    int memoization[6][v.size()];
    memset(memoization, -1, sizeof(memoization));

    //all rotations of the first rectangle can be used
    for (int i = 0; i < 6; ++i) {
        memoization[i][0] = v[0][i].coords[2];
    }

    //for each rectangle
    for (int i = 1; i < v.size(); ++i) {
        //for each possible permutation of the current rectangle
        for (int j = 0; j < 6; ++j) {
            //for each permutation of the previous rectangle
            for (int k = 0; k < 6; ++k) {
                rectangle &prev = v[i - 1][k];
                rectangle &curr = v[i][j];
                //is possible to put the current rectangle with the previous rectangle ?
                if( canStack(curr, prev) ) {
                    memoization[j][i] = std::max(memoization[j][i], curr.coords[2] + memoization[k][i-1]);
                }
            }
        }
    }

    //what is the best solution ?
    int ret = -1;
    for (int i = 0; i < 6; ++i) {
        ret = std::max(memoization[i][v.size()-1], ret);
    }
    return ret;
}

int main ( void ) {
    int n;
    scanf("%d", &n);

    std::vector< std::vector<rectangle>  > v(n);

    for (int i = 0; i < n; ++i) {
        rectangle r;
        scanf("%d %d %d", &r.coords[0], &r.coords[1], &r.coords[2]);

        //generate all rotations with the given rectangle (all combinations of the coordinates)
        for (int j = 0; j < 3; ++j)
            for (int k = 0; k < 3; ++k)
                if(j != k) //micro optimization disease
                    for (int l = 0; l < 3; ++l)
                        if(l != j && l != k)
                            v[i].push_back( rectangle(r.coords[j], r.coords[k], r.coords[l]) );

    }

    printf("%d\n", dp(v));
}

输入描述

A test case starts with an integer N, representing the number of boxes (1 ≤ N ≤ 10^5). Following there will be N rows, each containing three integers, A, B and C, representing the dimensions of the boxes (1 ≤ A, B, C ≤ 10^4).

输出描述

Print one row containing one integer, representing the maximum height of the stack if it’s possible to pile all the N boxes, or -1 otherwise.

示例输入

25 2 21 3 4

示例输出

6

给定输入和输出的示例图像。

Answer 1

通常，您会得到导致您失败的测试用例。否则，发现问题要困难得多。

你总是可以从不同的角度接近它!我将省略那些很容易复制的无聊部分。

struct Box { unsigned int dim[3]; };

Box 将存储每个...框的尺寸。当需要读取维度时，需要对其进行排序，以便 dim[0] >= dim[1] >= dim[2]。

想法是循环并在每次迭代时读取下一个框。然后它将新盒子的第二大尺寸与上一个盒子的第二大尺寸进行比较，并且与第三大尺寸相同。如果在任何一种情况下，较新的框较大，它都会调整较旧的框以比较第一大和第三大尺寸。如果那也失败了，那么第一和第二大。这样，它总是更喜欢使用更大的维度作为垂直维度。

如果它必须旋转一个框，它会转到下一个框并检查是否也不需要在那里调整旋转。它一直持续到没有更多的盒子或者不需要旋转下一个盒子为止。如果在任何时候，一个盒子的所有三个旋转都未能使其足够大，它就会停止，因为没有解决方案。

一旦所有框都就位，它只是总结每个框的垂直尺寸。

int main()
{
    unsigned int size; //num boxes
    std::cin >> size;

    std::vector<Box> boxes(size); //all boxes
    std::vector<unsigned char> pos(size, 0); //index of vertical dimension

    //gets the index of dimension that isn't vertical
    //largest indicates if it should pick the larger or smaller one
    auto get = [](unsigned char x, bool largest) { if (largest) return x == 0 ? 1 : 0; return x == 2 ? 1 : 2; };

    //check will compare the dimensions of two boxes and return true if the smaller one is under the larger one
    auto check = [&boxes, &pos, &get](unsigned int x, bool largest) { return boxes[x - 1].dim[get(pos[x - 1], largest)] < boxes[x].dim[get(pos[x], largest)]; };

    unsigned int x = 0, y; //indexing variables
    unsigned char change; //detects box rotation change
    bool fail = false; //if it cannot be solved
    for (x = 0; x < size && !fail; ++x)
    {
        //read in the next three dimensions
        //make sure dim[0] >= dim[1] >= dim[2]
        //simple enough to write
        //mine was too ugly and I didn't want to be embarrassed

        y = x;
        while (y && !fail) //when y == 0, no more boxes to check
        {
            change = pos[y - 1];
            while (check(y, true) || check(y, false)) //while invalid rotation
            {
                if (++pos[y - 1] == 3) //rotate, when pos == 3, no solution
                {
                    fail = true;
                    break;
                }
            }
            if (change != pos[y - 1]) //if rotated box
                --y;
            else
                break;
        }
    }
    if (fail)
    {
        std::cout << -1;
    }
    else
    {
        unsigned long long max = 0;
        for (x = 0; x < size; ++x)
            max += boxes[x].dim[pos[x]];
        std::cout << max;
    }
    return 0;
}

它适用于我编写的测试用例，但鉴于我不知道是什么原因导致您的失败，我无法告诉您我的有何不同(假设它也不会失败您的测试条件) .