मान लीजिए कि हमारे पास n वस्तुओं की एक सरणी है। प्रत्येक वस्तु की चौड़ाई W [i] होती है। हमें उन्हें पिरामिड के रूप में व्यवस्थित करना होगा जैसे -
-
ith की कुल चौड़ाई (i + 1)वें से कम है
-
ith में वस्तुओं की कुल संख्या (i + 1)वें से कम है
उदाहरण के लिए, यदि वज़न [40, 100, 20, 30] जैसा है, तो आउटपुट 2 होगा। तो शीर्ष स्तर 30 है, फिर निचला स्तर 20, 40 और 100
इसे हल करने के लिए, हम लालची दृष्टिकोण का उपयोग करेंगे। विचार यह है कि वस्तुओं को शीर्ष पर निचली चौड़ाई के साथ रखें, अगली वस्तु को नीचे के स्तर पर रखें और इसी तरह। स्तरों की अधिकतम संख्या प्राप्त करने के लिए, दिए गए सरणी को क्रमबद्ध करें और ऊपर से नीचे तक पिरामिड बनाने का प्रयास करें।
फिर क्रमबद्ध करने के बाद सरणी के पहले तत्व की तरह सरणी का सबसे छोटा तत्व ढूंढें, इसे शीर्ष पर रखें। फिर इसके नीचे के स्तरों को अधिक संख्या में वस्तुओं और अधिक चौड़ाई के साथ बनाने का प्रयास करें।
उदाहरण
#include <iostream>
#include <algorithm>
using namespace std;
int maxLevelPyramid(int objects[], int n) {
sort(objects, objects + n);
int ans = 1;
int prev_w = objects[0];
int count_p = 1;
int count_c = 0;
int curr_w = 0;
for (int i=1; i<n; i++){
curr_w += objects[i];
count_c++;
if (curr_w > prev_w && count_c > count_p){
prev_w = curr_w;
count_p = count_c;
count_c = curr_w = 0;
ans++;
}
}
return ans;
}
int main() {
int boxes[] = {40, 100, 20, 30};
int n = sizeof(boxes)/sizeof(boxes[0]);
cout << "Max level of pyramid: " << maxLevelPyramid(boxes, n);
} आउटपुट
Max level of pyramid: 2