我目前正在练习一些动态规划。 我遇到了“盒子堆栈”问题。
盒子被表示为：
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;
}