你会得到一组n种类型的矩形三维长方体，其中第i个长方体有高度h（i）、宽度w（i）和深度D（i）（所有实数）。您希望创建一个尽可能高的长方体堆栈，但如果较低长方体的二维基座尺寸严格大于较高长方体的二维基座尺寸，则只能将一个长方体堆叠在另一个长方体的顶部。当然，你可以旋转一个长方体，这样任何一边都可以作为它的基础。还允许使用同一类型长方体的多个实例。 资料来源： http://people.csail.mit.edu/bdean/6.046/dp/ .该链接还提供了一个视频来解释解决方案。
null
![图片[1]-箱子堆放问题| DP-22-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_boxstacking.png)
这个 箱子堆垛问题是LIS问题的一个变种 .我们需要建造一个最大高度的烟囱。 以下是问题陈述中需要注意的要点： 1） 只有当上部盒子的宽度和深度分别小于下部盒子的宽度和深度时，才能将盒子放在另一个盒子的顶部。 2） 我们可以旋转盒子，使其宽度小于深度。例如，如果有一个尺寸为{1x2x3}的盒子，其中1是高度，2×3是底部，那么可能有三种可能性，{1x2x3}，{2x1x3}和{3x1x2} 3） 我们可以使用多个盒子实例。这意味着，我们可以将一个盒子的两个不同旋转作为最大高度堆栈的一部分。 以下是 解决方案 基于 LIS问题的DP解法 .
方法1：使用表格的动态规划
1) 生成所有长方体的所有3个旋转。旋转数组的大小变为原始数组大小的3倍。为了简单起见，我们认为宽度总是小于或等于深度。 2) 按基本面积的降序对上述生成的3n个方框进行排序。 3) 在对箱子进行排序后，该问题与LIS相同，具有以下最优子结构特性。 MSH（i）=最大可能堆叠高度，盒子i位于堆叠顶部 MSH（i）={Max（MSH（j））+高度（i）}，其中j 宽度（i）和深度（j）>深度（i）。 如果没有这样的j，那么MSH（i）=高度（i） 4) 为了获得整体最大高度，我们返回max（MSH（i）），其中0 下面是上述解决方案的实现。
C++
/* Dynamic Programming implementation of Box Stacking problem */ #include<stdio.h> #include<stdlib.h> /* Representation of a box */ struct Box { // h --> height, w --> width, d --> depth int h, w, d; // for simplicity of solution, always keep w <= d }; // A utility function to get minimum of two integers int min ( int x, int y) { return (x < y)? x : y; } // A utility function to get maximum of two integers int max ( int x, int y) { return (x > y)? x : y; } /* Following function is needed for library function qsort(). We use qsort() to sort boxes in decreasing order of base area. Refer following link for help of qsort() and compare() int compare ( const void *a, const void * b) { return ( (*(Box *)b).d * (*(Box *)b).w ) - ( (*(Box *)a).d * (*(Box *)a).w ); } /* Returns the height of the tallest stack that can be formed with give type of boxes */ int maxStackHeight( Box arr[], int n ) { /* Create an array of all rotations of given boxes For example, for a box {1, 2, 3}, we consider three instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */ Box rot[3*n]; int index = 0; for ( int i = 0; i < n; i++) { // Copy the original box rot[index].h = arr[i].h; rot[index].d = max(arr[i].d, arr[i].w); rot[index].w = min(arr[i].d, arr[i].w); index++; // First rotation of box rot[index].h = arr[i].w; rot[index].d = max(arr[i].h, arr[i].d); rot[index].w = min(arr[i].h, arr[i].d); index++; // Second rotation of box rot[index].h = arr[i].d; rot[index].d = max(arr[i].h, arr[i].w); rot[index].w = min(arr[i].h, arr[i].w); index++; } // Now the number of boxes is 3n n = 3*n; /* Sort the array 'rot[]' in non-increasing order of base area */ qsort (rot, n, sizeof (rot[0]), compare); // Uncomment following two lines to print all rotations // for (int i = 0; i < n; i++ ) // printf("%d x %d x %d", rot[i].h, rot[i].w, rot[i].d); /* Initialize msh values for all indexes msh[i] --> Maximum possible Stack Height with box i on top */ int msh[n]; for ( int i = 0; i < n; i++ ) msh[i] = rot[i].h; /* Compute optimized msh values in bottom up manner */ for ( int i = 1; i < n; i++ ) for ( int j = 0; j < i; j++ ) if ( rot[i].w < rot[j].w && rot[i].d < rot[j].d && msh[i] < msh[j] + rot[i].h ) { msh[i] = msh[j] + rot[i].h; } /* Pick maximum of all msh values */ int max = -1; for ( int i = 0; i < n; i++ ) if ( max < msh[i] ) max = msh[i]; return max; } /* Driver program to test above function */ int main() { Box arr[] = { {4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32} }; int n = sizeof (arr)/ sizeof (arr[0]); printf ( "The maximum possible height of stack is %d" , maxStackHeight (arr, n) ); return 0; } |
JAVA
/* Dynamic Programming implementation of Box Stacking problem in Java*/ import java.util.*; public class GFG { /* Representation of a box */ static class Box implements Comparable<Box>{ // h --> height, w --> width, // d --> depth int h, w, d, area; // for simplicity of solution, // always keep w <= d /*Constructor to initialise object*/ public Box( int h, int w, int d) { this .h = h; this .w = w; this .d = d; } /*To sort the box array on the basis of area in decreasing order of area */ @Override public int compareTo(Box o) { return o.area- this .area; } } /* Returns the height of the tallest stack that can be formed with give type of boxes */ static int maxStackHeight( Box arr[], int n){ Box[] rot = new Box[n* 3 ]; /* New Array of boxes is created - considering all 3 possible rotations, with width always greater than equal to width */ for ( int i = 0 ;i < n;i++){ Box box = arr[i]; /* Original Box*/ rot[ 3 *i] = new Box(box.h, Math.max(box.w,box.d), Math.min(box.w,box.d)); /* First rotation of box*/ rot[ 3 *i + 1 ] = new Box(box.w, Math.max(box.h,box.d), Math.min(box.h,box.d)); /* Second rotation of box*/ rot[ 3 *i + 2 ] = new Box(box.d, Math.max(box.w,box.h), Math.min(box.w,box.h)); } /* Calculating base area of each of the boxes.*/ for ( int i = 0 ; i < rot.length; i++) rot[i].area = rot[i].w * rot[i].d; /* Sorting the Boxes on the bases of Area in non Increasing order.*/ Arrays.sort(rot); int count = 3 * n; /* Initialize msh values for all indexes msh[i] --> Maximum possible Stack Height with box i on top */ int []msh = new int [count]; for ( int i = 0 ; i < count; i++ ) msh[i] = rot[i].h; /* Computing optimized msh[] values in bottom up manner */ for ( int i = 0 ; i < count; i++){ msh[i] = 0 ; Box box = rot[i]; int val = 0 ; for ( int j = 0 ; j < i; j++){ Box prevBox = rot[j]; if (box.w < prevBox.w && box.d < prevBox.d){ val = Math.max(val, msh[j]); } } msh[i] = val + box.h; } int max = - 1 ; /* Pick maximum of all msh values */ for ( int i = 0 ; i < count; i++){ max = Math.max(max, msh[i]); } return max; } /* Driver program to test above function */ public static void main(String[] args) { Box[] arr = new Box[ 4 ]; arr[ 0 ] = new Box( 4 , 6 , 7 ); arr[ 1 ] = new Box( 1 , 2 , 3 ); arr[ 2 ] = new Box( 4 , 5 , 6 ); arr[ 3 ] = new Box( 10 , 12 , 32 ); System.out.println( "The maximum possible " + "height of stack is " + maxStackHeight(arr, 4 )); } } // This code is contributed by Divyam |
Python3
# Dynamic Programming implementation # of Box Stacking problem class Box: # Representation of a box def __init__( self , h, w, d): self .h = h self .w = w self .d = d def __lt__( self , other): return self .d * self .w < other.d * other.w def maxStackHeight(arr, n): # Create an array of all rotations of # given boxes. For example, for a box {1, 2, 3}, # we consider three instances{{1, 2, 3}, # {2, 1, 3}, {3, 1, 2}} rot = [Box( 0 , 0 , 0 ) for _ in range ( 3 * n)] index = 0 for i in range (n): # Copy the original box rot[index].h = arr[i].h rot[index].d = max (arr[i].d, arr[i].w) rot[index].w = min (arr[i].d, arr[i].w) index + = 1 # First rotation of the box rot[index].h = arr[i].w rot[index].d = max (arr[i].h, arr[i].d) rot[index].w = min (arr[i].h, arr[i].d) index + = 1 # Second rotation of the box rot[index].h = arr[i].d rot[index].d = max (arr[i].h, arr[i].w) rot[index].w = min (arr[i].h, arr[i].w) index + = 1 # Now the number of boxes is 3n n * = 3 # Sort the array 'rot[]' in non-increasing # order of base area rot.sort(reverse = True ) # Uncomment following two lines to print # all rotations # for i in range(n): # print(rot[i].h, 'x', rot[i].w, 'x', rot[i].d) # Initialize msh values for all indexes # msh[i] --> Maximum possible Stack Height # with box i on top msh = [ 0 ] * n for i in range (n): msh[i] = rot[i].h # Compute optimized msh values # in bottom up manner for i in range ( 1 , n): for j in range ( 0 , i): if (rot[i].w < rot[j].w and rot[i].d < rot[j].d): if msh[i] < msh[j] + rot[i].h: msh[i] = msh[j] + rot[i].h maxm = - 1 for i in range (n): maxm = max (maxm, msh[i]) return maxm # Driver Code if __name__ = = "__main__" : arr = [Box( 4 , 6 , 7 ), Box( 1 , 2 , 3 ), Box( 4 , 5 , 6 ), Box( 10 , 12 , 32 )] n = len (arr) print ( "The maximum possible height of stack is" , maxStackHeight(arr, n)) # This code is contributed by vibhu4agarwal |
输出
The maximum possible height of stack is 60
在上面的程序中，给定的输入框是{4,6,7}，{1,2,3}，{4,5,6}，{10,12,32}。以下是所有盒子的旋转，按基底面积的降序排列。
10 x 12 x 32 12 x 10 x 32 32 x 10 x 12 4 x 6 x 7 4 x 5 x 6 6 x 4 x 7 5 x 4 x 6 7 x 4 x 6 6 x 4 x 5 1 x 2 x 3 2 x 1 x 3 3 x 1 x 2
高度60由方框{{ 3. , 1, 2}, { 1. , 2, 3}, { 6. , 4, 5}, { 4. , 5, 6}, { 4. , 6, 7}, { 32 , 10, 12}, { 10 , 12, 32}} 时间复杂度：O（n^2） 辅助空间：O（n）
方法2：使用记忆的动态规划（自上而下）
C++
/* Dynamic Programming top-down implementation of Box * Stacking problem */ #include <bits/stdc++.h> using namespace std; /* Representation of a box */ class Box { public : int length; int width; int height; }; // dp array int dp[303]; /* boxes -> vector of Box bottom_box_index -> index of the bottom box index -> index of current box */ /* NOTE: we can use only one variable in place of bottom_box_index and index but it has been avoided to make it simple */ int findMaxHeight(vector<Box>& boxes, int bottom_box_index, int index) { // base case if (index < 0) return 0; if (dp[index] != -1) return dp[index]; int maximumHeight = 0; // recurse for ( int i = index; i >= 0; i--) { // if there is no bottom box if (bottom_box_index == -1 // or if length & width of new box is < that of // bottom box || (boxes[i].length < boxes[bottom_box_index].length && boxes[i].width < boxes[bottom_box_index].width)) maximumHeight = max(maximumHeight, findMaxHeight(boxes, i, i - 1) + boxes[i].height); } return dp[index] = maximumHeight; } /* wrapper function for recursive calls which Returns the height of the tallest stack that can be formed with give type of boxes */ int maxStackHeight( int height[], int width[], int length[], int types) { // creating a vector of type Box class vector<Box> boxes; // Initialize dp array with -1 memset (dp, -1, sizeof (dp)); Box box; /* Create an array of all rotations of given boxes For example, for a box {1, 2, 3}, we consider three instances{{1, 2, 3}, {2, 1, 3}, {3, 1, 2}} */ for ( int i = 0; i < types; i++) { // copy original box box.height = height[i]; box.length = max(length[i], width[i]); box.width = min(length[i], width[i]); boxes.push_back(box); // First rotation of box box.height = width[i]; box.length = max(length[i], height[i]); box.width = min(length[i], height[i]); boxes.push_back(box); // Second rotation of box box.height = length[i]; box.length = max(width[i], height[i]); box.width = min(width[i], height[i]); boxes.push_back(box); } // sort by area in ascending order .. because we will be dealing with this vector in reverse sort(boxes.begin(), boxes.end(), [](Box b1, Box b2) { // if area of box1 < area of box2 return (b1.length * b1.width) < (b2.length * b2.width); }); // Uncomment following two lines to print all rotations //for (int i = boxes.size() - 1; i >= 0; i-- ) // printf("%d x %d x %d", boxes[i].length, boxes[i].width, boxes[i].height); return findMaxHeight(boxes, -1, boxes.size() - 1); } int main() { // where length, width and height of a particular box // are at ith index of the following arrays int length[] = { 4, 1, 4, 10 }; int width[] = { 6, 2, 5, 12 }; int height[] = { 7, 3, 6, 32 }; int n = sizeof (length) / sizeof (length[0]); printf ( "The maximum possible height of stack is %d" , maxStackHeight(height, length, width, n)); return 0; } |
输出
The maximum possible height of stack is 60
在上面的程序中，对于尺寸为{4,6,7}，{1,2,3}，{4,5,6}，{10,12,32}的盒子，输入长度为{4,1,4,10}，宽度为{6,2,5,12}，高度为{7,3,6,32}。盒子可以按基面积的降序进行以下旋转。
32 x 12 x 10 <-32 x 10 x 1212 x 10 x 32 <-7 x 6 x 4 <-6 x 5 x 4 <-7 x 4 x 66 x 4 x 56 x 4 x 75 x 4 x 6 <-3 x 2 x 1 <-3 x 1 x 22 x 1 x 3 <-The maximum possible height of stack is 60
高度60由方框{2,1,3}，{3,2,1}，{5,4,6}，{6,5,4}，{7,6,4}，{12,10,32}，{32,12,10}获得
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
