এই সমস্যায় বিভিন্ন বক্সের একটি সেট দেওয়া থাকে, যাদের দৈর্ঘ্য, প্রস্থ এবং উঁচু ভিন্ন হতে পারে। আমাদের কাজ হলো একটি বক্স স্ট্যাক খুঁজে বের করা যাতে এর উঁচু όσο সম্ভব বেশি হয়। আমরা ইচ্ছেমতো কোনো বক্সকে ঘুরিয়ে দিতে পারি। কিন্তু একটি নিয়ম মানতে হবে।
একটি বক্সকে অন্য বক্সের ওপর রাখা যাবে যদি নিচের বক্সের উপরের সারফেসের এলাকা উপরের বক্সের নিচের এলাকার চেয়ে বড় হয়।
ইনপুট এবং আউটপুট
ইনপুট: বক্সের একটি লিস্ট দেওয়া আছে। প্রতিটি বক্সকে (length, breadth, height) দিয়ে চিহ্নিত করা হয়।
{ (4, 6, 7), (1, 2, 3), (4, 5, 6), (10, 12, 32) }
আউটপুট: বক্স স্ট্যাকের সর্বাধিক সম্ভাব্য উঁচু: 60
এলগরিদম
maxHeight(boxList, n)
ইনপুট: ভিন্ন বক্সের তালিকা, বক্সের সংখ্যা।
আউটপুট: বক্স স্ট্যাকিং দিয়ে পাওয়া সর্বাধিক উঁচু।
শুরু
3n আকারের একটি রোটেশন অ্যারে rot সংজ্ঞায়িত করুন।
index := 0
boxList-এ সব বক্স i এর জন্য, করুন
rot[index].len := boxList[i].len
rot[index].hei := max(boxList[i].hei, boxList[i].bre)
rot[index].bre := min(boxList[i].hei, boxList[i].bre)
index := index + 1
rot[index].len := boxList[i].bre
rot[index].hei := max(boxList[i].len, boxList[i].hei)
rot[index].bre := min(boxList[i].len, boxList[i].hei)
index := index + 1
rot[index].len := boxList[i].hei
rot[index].hei := max(boxList[i].len, boxList[i].bre)
rot[index].bre := min(boxList[i].len, boxList[i].bre)
index := index + 1
n := 3n
rot লিস্টকে সর্ট করুন
maxHeightTemp অ্যারে সংজ্ঞায়িত করুন
i := 1 থেকে n-1 পর্যন্ত, করুন
j := 0 থেকে i-1 পর্যন্ত, করুন
যদি rot[i].bre < rot[j].bre এবং
rot[i].hei < rot[j].hei এবং
maxHeightTemp[i] < maxHeightTemp[j] + rot[i].len, তবে
maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len
শর্ত শেষ
শেষ লুপ
শেষ লুপ
maxHeight := -1
i := 0 থেকে n-1 পর্যন্ত, করুন
যদি maxHeight < maxHeightTemp[i], তবে
maxHeight := maxHeightTemp[i]
শর্ত শেষ
শেষ লুপ
return maxHeight
শেষ
উদাহরণ (C++ কোড)
#include <iostream>
#include <algorithm>
using namespace std;
struct Box {
int length, breadth, 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; // বক্সকে উঁচু অনুযায়ী ডিসেন্ডিং অর্ডারে সর্ট করতে
}
int maxHeight(Box boxList[], int n) {
Box rotation[3*n]; // একটি বক্স ৩ ভাবে ঘুরানো যায়, তাই ৩n সংখ্যক রোটেশন
int index = 0;
for (int i = 0; i < n; i++) {
// বক্সের প্রাথমিক অবস্থা স্টোর করুন
rotation[index].length = boxList[i].length;
rotation[index].height = max(boxList[i].height, boxList[i].breadth);
rotation[index].breadth = min(boxList[i].height, boxList[i].breadth);
index++;
// প্রথম রোটেশনের পর ডাইমেনশন
rotation[index].length = boxList[i].breadth;
rotation[index].height = max(boxList[i].length, boxList[i].height);
rotation[index].breadth = min(boxList[i].length, boxList[i].height);
index++;
// দ্বিতীয় রোটেশনের পর ডাইমেনশন
rotation[index].length = boxList[i].height;
rotation[index].height = max(boxList[i].length, boxList[i].breadth);
rotation[index].breadth = min(boxList[i].length, boxList[i].breadth);
index++;
}
n = 3*n; // প্রতিটি বক্সের ৩টি রোটেশনের জন্য n কে 3n হিসেবে সেট করুন
sort(rotation, rotation+n, compare); // রোটেশন অ্যারেকে ডিসেন্ডিং অর্ডারে সর্ট করুন
int maxHTemp[n]; // 임시 max height যদি i-তম বক্স স্ট্যাক করা হয়
for (int i = 0; i < n; i++)
maxHTemp[i] = rotation[i].length;
for (int i = 1; i < n; i++) // অপ্টিমাইজড স্ট্যাক উঁচু খুঁজে বের করুন
for (int j = 0; j < i; j++)
if (rotation[i].breadth < rotation[j].breadth &&
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++) // সব টেম্পোরারি উঁচু থেকে সর্বোচ্চ উঁচু খুঁজে বের করুন
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
