箱子堆叠问题
在这个问题中给定了一组不同的盒子,不同盒子的长度、宽度和高度可能不同。我们的任务是找到一叠这些盒子的高度尽可能大。我们可以根据需要旋转任何盒子。但有一条规则需要遵守。
只有当底部盒子的顶部面积大于顶部盒子的底部面积时,才能将一个盒子放在另一个盒子上。
输入和输出
Input: A list of boxes is given. Each box is denoted by (length, bredth, height). { (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) } Output: The maximum possible height of box stack is: 60
算法
maxHeight(boxList, n)
输入 − 不同盒子列表、盒子数。
输出 −通过堆叠盒子找到的最大高度。
Begin define rotation array rot of size 3n. index := 0 for all boxes i, in the boxList, do rot[index].len := boxList[i].len rot[index].hei := maximum of boxList[i].hei and boxList[i].bre rot[index].bre := minimum of boxList[i].hei and boxList[i].bre index := index + 1 rot[index].len := boxList[i].bre rot[index].hei := maximum of boxList[i].len and boxList[i].hei rot[index].bre := minimum of boxList[i].len and boxList[i].hei index := index + 1 rot[index].len := boxList[i].hei rot[index].hei := maximum of boxList[i].len and boxList[i].bre rot[index].bre := minimum of boxList[i].len and boxList[i].bre index := index + 1 n := 3n sort the rot list define maxHeightTemp array for i := 1 to n-1, do for j := 0 to i-1, do if rot[i].bre < rot[j].bre AND rot[i].hei < rot[j].hei AND maxHeightTemp[i] < maxHeightTemp + rot[i].len, then maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len done done maxHeight := -1 for i := 0 to n-1, do if maxHeight < maxHeightTemp[i], then maxHeight := maxHeightTemp[i] done done return maxHeight End
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
示例
#include<iostream> #include<algorithm> using namespace std; struct Box { int length, bredth, height; }; int min (int x, int y) { return (x < y)? x : y; } int max (int x, int y) { return (x > y)? x : y; } bool compare(Box b1, Box b2) { return b1.height > b2.height; //to sort the box as descending order of height } int maxHeight( Box boxList[], int n ) { Box rotation[3*n]; //a box can be rotared as 3 type, so there is 3n number of rotations int index = 0; for (int i = 0; i < n; i++) { //store initial position of the box rotation[index].length = boxList[i].length; rotation[index].height = max(boxList[i].height, boxList[i].bredth); rotation[index].bredth = min(boxList[i].height, boxList[i].bredth); index++; //dimention after first rotation rotation[index].length = boxList[i].bredth; rotation[index].height = max(boxList[i].length, boxList[i].height); rotation[index].bredth = min(boxList[i].length, boxList[i].height); index++; //Dimention after second rotation rotation[index].length = boxList[i].height; rotation[index].height = max(boxList[i].length, boxList[i].bredth); rotation[index].bredth = min(boxList[i].length, boxList[i].bredth); index++; } n = 3*n; //set n as 3n for 3 rotations of each boxes sort(rotation, rotation+n, compare); //sort rotation array as descending order int maxHTemp[n]; //temporary max height if ith box is stacked for (int i = 0; i < n; i++ ) maxHTemp[i] = rotation[i].length; for (int i = 1; i < n; i++ ) //find optimized stack height for (int j = 0; j < i; j++ ) if ( rotation[i].bredth < rotation[j].bredth && rotation[i].height < rotation[j].height && maxHTemp[i] < maxHTemp[j] + rotation[i].length) { maxHTemp[i] = maxHTemp[j] + rotation[i].length; } int maxHeight = -1; for ( int i = 0; i < n; i++ ) //find the maximum height from all temporary heights if ( maxHeight < maxHTemp[i] ) maxHeight = maxHTemp[i]; return maxHeight; } int main() { Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} }; int n = 4; cout<<"The maximum possible height of box stack is: " << maxHeight (arr, n) << endl; }
输出
The maximum possible height of box stack is: 60
广告