สมมติว่าเรามีอาร์เรย์ของ 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
