इस समस्या में विभिन्न बॉक्सों का एक समुच्चय दिया गया है, अलग-अलग बॉक्सों के लिए लंबाई, चौड़ाई और ऊंचाई भिन्न हो सकती है। हमारा कार्य इन बॉक्सों का एक स्टैक ढूंढना है, जिसकी ऊंचाई यथासंभव अधिक हो। हम किसी भी बॉक्स को अपनी इच्छानुसार घुमा सकते हैं। लेकिन एक नियम बनाए रखना होगा।
एक बॉक्स को दूसरे बॉक्स पर रखा जा सकता है यदि नीचे वाले बॉक्स की ऊपरी सतह का क्षेत्रफल ऊपर वाले बॉक्स के निचले क्षेत्रफल से बड़ा है।
इनपुट और आउटपुट
इनपुट: बॉक्सों की एक सूची दी गई है। प्रत्येक बॉक्स को (लंबाई, चौड़ाई, ऊंचाई) से दर्शाया गया है। { (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 := boxList[i].hei और boxList[i].bre का अधिकतम rot[index].bre := boxList[i].hei और boxList[i].bre का न्यूनतम index := index + 1 rot[index].len := boxList[i].bre rot[index].hei := boxList[i].len और boxList[i].hei का अधिकतम rot[index].bre := boxList[i].len और boxList[i].hei का न्यूनतम index := index + 1 rot[index].len := boxList[i].hei rot[index].hei := boxList[i].len और boxList[i].bre का अधिकतम rot[index].bre := 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 AND rot[i].hei < rot[j].hei AND maxHeightTemp[i] < maxHeightTemp + rot[i].len, तो maxHeightTemp[i] := maxHeightTemp[j] + rot[i].len किया किया maxHeight := -1 i := 0 से n-1 तक, करें यदि maxHeight < maxHeightTemp[i], तो maxHeight := maxHeightTemp[i] किया किया maxHeight वापस करें अंत
उदाहरण
#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; //ऊंचाई के अवरोही क्रम में बॉक्स को क्रमबद्ध करने के लिए } int maxHeight( Box boxList[], int n ) { Box rotation[3*n]; //एक बॉक्स को 3 प्रकार से घुमाया जा सकता है, इसलिए 3n संख्या में रोटेशन हैं 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].bredth); rotation[index].bredth = min(boxList[i].height, boxList[i].bredth); index++; //पहले रोटेशन के बाद आयाम 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++; //दूसरे रोटेशन के बाद आयाम 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; //n को 3n सेट करें क्योंकि प्रत्येक बॉक्स के 3 रोटेशन हैं sort(rotation, rotation+n, compare); //रोटेशन सरणी को अवरोही क्रम में क्रमबद्ध करें int maxHTemp[n]; //अस्थायी अधिकतम ऊंचाई यदि 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].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++ ) //सभी अस्थायी ऊंचाइयों से अधिकतम ऊंचाई खोजें 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
