The box stacking problem is also well-known as the dynamic programming challenge. It asks the users to determine the highest stack of boxes that may be stacked on top of one another. The only way a box can be stacked atop another is if its base area is smaller, and even then, only when the box is rotated.
- Formulation of the problem: Given a collection of boxes and their dimensions (length, breadth, and height), the objective is to determine the highest height that can be achieved by stacking the boxes while adhering to the restrictions.
- Generating rotations: It is necessary to create every conceivable rotation for each box to handle the rotation of the boxes. As a result, we can think about various box orientations when stacking. The three possible rotations for each box allow for a variety of stacking configurations.
- Methodology based on dynamic programming: This method is used to determine the highest height that can be reached. The problem can be resolved using the dynamic programming methodology by establishing a state that symbolizes the highest height that can be achieved while taking the current box at the top into consideration. When examining the boxes below a given box, we keep track of the highest height that may be achieved for each one. The current box is compared to all the boxes below it during the dynamic programming state change, and the maximum height is then updated appropriately.
- Implementation of the algorithm: The procedure is often implemented using a combination of data structures, such as vectors or arrays, to record the box dimensions and dynamic programming arrays, which maintain track of the highest height that may be achieved. The method cycles over the boxes and determines the highescpp tutorial that can be reached while taking the limits placed on it by the issue.
- Output and analysis: After the algorithm has processed all the boxes, it provides the highest height that can be attained by stacking the boxes. The Box Stacking Problem's resolution for the specified set of boxes is represented by this output.
- Sorting based on base area: After all rotations have been created, the boxes are arranged in a non-increasing manner according to their base areas. This method of sorting makes sure that a smaller base area box can only be stacked on top of a larger base area box.
Code:
Let's consider a scenario to demonstrate the box stacking issue in C++:
Example
#include <cstdlib>
#include <iostream>
#include <memory>
#include <vector>
#include <algorithm>
using namespace std;
class dim_ension;
typedef shared_ptr<vector<dim_ension*> > PVecDim;
typedef vector<dim_ension*> VecDim;
typedef vector<dim_ension*>::iterator Vec_DimIter;
typedef shared_ptr<vector<int> > PVecInt;
typedef vector<int> VecInt;
typedef vector<int>::iterator Vec_IntIter;
typedef shared_ptr<vector<dim_ension> > PDim;
typedef vector<dim_ension> Dim;
typedef vector<dim_ension>::iterator DimIter;
struct dim_ension {
int height, width, length;
dim_ension(int h, int w, int l) : height(h), width(w), length(l) {
}
dim_ension() : dim_ension(0,0,0) {
}
};
class Base_Comparator
{
public:
bool operator() (const dim_ension& a, const dim_ension& b)
{
if(a.width*a.length > b.width*b.length)
return true;
else
return false;
}
};
class Box_Stacking
{
public:
int doBox_Stacking(PVecDim inList)
{
int i,j;
Vec_DimIter it;
cout<<"Input List elements are"<<endl;
for (it = inList->begin(); it != inList->end(); ++it)
{
cout<<(*it)->height<<" "<<(*it)->length<<" "<<(*it)->width<<endl;
}
PDim modList = getModList(inList);
sort(modList->begin(), modList->end(), compare) ;
cout<<"Sorted List elements are" <<endl;
DimIter dit;
for(dit=modList->begin();dit!=modList->end();++dit)
{
cout<<(*dit).height<<" "<<(*dit).length<<" "<<(*dit).width<<" "<<endl;
}
M->reserve(modList->size());
M->resize(modList->size());
vector<int> prev(modList->size(), -1);
(*M)[0] = (*modList)[0].height;
for(i=1;i<modList->size();++i)
{
(*M)[i] = (*modList)[i].height;
int max = (*M)[i];
for(j=i-1;j>=0;--j)
{
if((((*modList)[i].length < (*modList)[j].length) &&
(*modList)[i].width < (*modList)[j].width) ||
(((*modList)[i].length < (*modList)[j].width) &&
(*modList)[i].width < (*modList)[j].length))
{
if(max < ((*M)[i] + (*M)[j]))
{
max = (*M)[i] + (*M)[j];
prev[i] = j;
}
}
}
(*M)[i] = max;
}
int ret = findMax();
prepare_OutList(modList, prev, ret);
return (*M)[ret];
}
Box_Stacking() : mOutList(new Dim()) , M(new VecInt()) {
}
friend ostream& operator<<(ostream& out, const Box_Stacking& bs)
{
DimIter it;
out<<"Output list elements are "<<endl;
for(it = bs.mOutList->begin(); it!=bs.mOutList->end(); ++it)
{
out<<"{"<<(*it).height<<","<<(*it).width<<","<<(*it).length<<"}"<<endl;
}
return out;
}
private:
PDim mOutList;
PVecInt M;
Base_Comparator compare;
PDim getModList(PVecDim inList)
{
PDim modList(new Dim());
Vec_DimIter it;
int j=0;
for(it = inList->begin(); it!=inList->end(); ++it)
{
dim_ension rot1((*it)->width, (*it)->height, (*it)->length);
dim_ension rot2((*it)->length, (*it)->width, (*it)->height);
modList->push_back(*(*it));
modList->push_back(rot1);
modList->push_back(rot2);
}
return modList;
}
int findMax()
{
int max=-1, pos;
for(int i=0;i<(M)->size();i++)
{
if((*M)[i] >= max)
{
pos = i;
max = (*M)[i];
}
}
return pos;
}
void prepare_OutList(PDim modList, vector<int> prev, int pos)
{
while(pos != -1)
{
mOutList->push_back((*modList)[pos]);
pos = prev[pos];
}
}
};
int main(void)
{
dim_ension d[] = {{4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}};
//dimension d[] = {{1,7,9}, {6,3,5}, {10,2,4 }};
shared_ptr<Box_Stacking> bs(new Box_Stacking());
PVecDim vecdim(new VecDim());
for (int i=0;i<sizeof(d)/sizeof(d[0]); ++i)
{
vecdim->push_back(&d[i]);
}
int max_height = bs->doBox_Stacking(vecdim);
cout<<"Max height is "<<max_height<<endl<<*bs;
return EXIT_SUCCESS;
}
Output:
Output
Input List elements are
4 7 6
1 3 2
4 6 5
10 32 12
Sorted List elements are
10 32 12
12 32 10
32 10 12
4 7 6
4 6 5
6 7 4
7 4 6
5 6 4
6 4 5
1 3 2
2 3 1
3 1 2
Max height is 60
Output list elements are
{3,2,1}
{1,2,3}
{6,5,4}
{4,5,6}
{4,6,7}
{32,12,10}
{10,12,32}
Utilizing shared pointers and distinct classes to address the Box Stacking Problem involves the implementation of a BoxStacking class for managing the stacking procedure and a dimension struct to define box dimensions. Through the utilization of dynamic programming, this method calculates the maximum achievable height for box stacking by sorting the boxes based on their base area. Additionally, it generates a list of boxes that contribute to the highest height. The primary function outputs the maximum height and the corresponding list of contributing boxes, demonstrating the usage of the Box_Stacking class with a set of sample boxes.
