c++ - 堆栈盒-动态编程

我目前正在练习一些动态编程。我碰到了一堆箱子。
这些框表示为:

struct Box{
    double h;
    double w;
    double d;
};

问题是要创建最高的箱子堆，其中堆中的每个箱子(在宽度和深度上)都比上面的箱子大。假设在这种情况下，框无法旋转。

我将盒子存储在std::vector<Box>中。我首先要按照宽度然后按深度进行稳定排序，以便每当我选择一个框时，我都只需要向前搜索适合的下一个框即可。

这是我的问题-这是最佳选择吗？
我想每次我选一个盒子时，我都需要搜索线性时间(O(n))才能选出下一个可能的盒子。
有没有其他方法可以存储时间复杂度更高的盒子？

当然也欢迎任何其他优化。

我的完整代码:

//Get index of next box that fits or -1 if none
int getP(std::vector<Box>& boxes, int n){
    double n_w = boxes[n].w;
    double n_d = boxes[n].d;
    for (int i=n-1; i >= 0; i--){
        if (n_w > boxes[i].w && n_d > boxes[i].d)
            return i;
    }
    return -1;
}

//Get highest possible stack.
double stackOfBoxes(std::vector<Box>& boxes, int n, Box* bottom){
    if (n == -1)
        return 0;
    if (bottom == NULL || (bottom->d > boxes[n].d && bottom->w > boxes[n].w))
        return max(stackOfBoxes(boxes, n-1, bottom),stackOfBoxes(boxes, getP(boxes,n), &boxes[n])+boxes[n].h);
    else
        return stackOfBoxes(boxes, n-1, bottom);
}


int main(){
    std::vector<Box> boxes = { {3,1,1},{5,2,2},{10,7,7} };
    std::stable_sort(boxes.begin(), boxes.end(), sortByW);
    std::stable_sort(boxes.begin(), boxes.end(), sortByD);

    cout << stackOfBoxes(boxes, 2, NULL) << endl;
}

最佳答案

不正确

我用相同的输入尝试了您的代码，但我制作了0.5的第三个框的深度除外。

Here is the result。它给出了15，答案应该是10，因为没有其他盒子可以放在第三个盒子的顶部。

关于c++ - 堆栈盒-动态编程，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/39043036/