Se le da un conjunto de n tipos de cajas tridimensionales rectangulares, donde la i^-ésima caja tiene una altura h (i), un ancho w (i) y una profundidad d (i) (todos números reales). Desea crear una pila de cajas que sea lo más alta posible, pero solo puede apilar una caja encima de otra caja si las dimensiones de la base 2-D de la caja inferior son estrictamente mayores que las de la base 2-D. D base de la caja superior. Por supuesto, puede rotar una caja para que cualquier lado funcione como su base. También está permitido usar varias instancias del mismo tipo de caja.
Fuente: http://people.csail.mit.edu/bdean/6.046/dp/ . El enlace también tiene un video para una explicación de la solución.
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()
http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */
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\n", 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\n",
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
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\n", 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\n",
maxStackHeight(height, length, width, n));
return 0;
}
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA