বক্স স্ট্যাকিং সমস্যা

এই সমস্যায় বিভিন্ন বাক্সের একটি সেট দেওয়া হয়েছে, বিভিন্ন বাক্সের দৈর্ঘ্য, প্রস্থ এবং প্রস্থ ভিন্ন হতে পারে। আমাদের কাজ হল এই বাক্সগুলির একটি স্ট্যাক খুঁজে বের করা, যার উচ্চতা যতটা সম্ভব। আমরা আমাদের ইচ্ছামতো যেকোনো বক্স ঘোরাতে পারি। কিন্তু বজায় রাখার একটা নিয়ম আছে।

নীচের বাক্সের উপরের পৃষ্ঠের ক্ষেত্রফল উপরের বাক্সের নীচের অংশের চেয়ে বড় হলে একজন অন্য বাক্সে একটি বাক্স রাখতে পারে।

ইনপুট এবং আউটপুট

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

উদাহরণ

#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