Giả sử chúng ta có một mảng gồm n đối tượng. Mỗi đối tượng có chiều rộng W [i]. Chúng ta phải sắp xếp chúng theo một hình chóp như -
-
Tổng chiều rộng của thứ i nhỏ hơn (i + 1) thứ
-
Tổng số đối tượng trong thứ i nhỏ hơn (i + 1) thứ
Ví dụ:nếu các trọng số như [40, 100, 20, 30], thì đầu ra sẽ là 2. Vì vậy, cấp cao nhất là 30, sau đó cấp thấp hơn 20, 40 và 100
Để giải quyết điều này, chúng ta sẽ sử dụng phương pháp tham lam. Ý tưởng là sử dụng đặt các đối tượng có chiều rộng thấp hơn ở trên cùng, đối tượng tiếp theo ở cấp ngay bên dưới, v.v. Để nhận được số cấp tối đa, hãy sắp xếp mảng đã cho và cố gắng tạo hình kim tự tháp từ trên xuống dưới.
Sau đó tìm phần tử nhỏ nhất của mảng như phần tử đầu tiên của mảng sau khi sắp xếp, đặt nó lên trên cùng. Sau đó, cố gắng xây dựng các cấp bên dưới nó với số lượng đối tượng lớn hơn và chiều rộng lớn hơn.
Ví dụ
#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);
} Đầu ra
Max level of pyramid: 2