ধরুন আমাদের n অবজেক্টের একটি অ্যারে আছে। প্রতিটি বস্তুর প্রস্থ W[i] আছে। আমাদের সেগুলিকে পিরামিডের মতো সাজাতে হবে −
-
ith এর মোট প্রস্থ (i + 1)th
এর চেয়ে কম -
ith-এ মোট বস্তুর সংখ্যা (i + 1)th
এর চেয়ে কম
উদাহরণস্বরূপ, যদি ওজনগুলি [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
