c++ - 一堆盒子 - 动态规划

Question

我目前正在练习一些动态规划。我遇到了一堆盒子。
这些框表示为:

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;
}

Answer 1

And here is my question - Is this optimal?

这是不正确的。

我用相同的输入尝试了您的代码，除了我将第三个框的深度设置为 0.5。

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