Рубрики

Найти максимальную высоту пирамиды из заданного массива объектов

Учитывая n объектов, каждый объект имеет ширину w i . Нам нужно расположить их пирамидально так, чтобы:

  1. Общая ширина i- го меньше (i + 1) -ого .
  2. Общее количество объектов в i- ом меньше (i + 1) -ого .

Задача — найти максимальную высоту, которая может быть достигнута от заданных объектов.

Примеры :

Input : arr[] = {40, 100, 20, 30}
Output : 2
Top level : 30.
Lower (or bottom) level : 20, 40 and 100
Other possibility can be placing
20 on the top, and at second level any
other 4 objects. Another possibility is
to place 40 at top and other three at the
bottom.

Input : arr[] = {10, 20, 30, 50, 60, 70}
Output : 3

Идея состоит в том, чтобы использовать жадный подход, поместив объект с наименьшей шириной вверху, следующий объект на уровне справа внизу и так далее.
Чтобы найти максимальное количество уровней, отсортируйте данный массив и попробуйте сформировать пирамиду сверху вниз. Найдите наименьший элемент массива, т.е. первый элемент массива после сортировки, поместите его сверху. Затем попробуйте построить уровни ниже этого с большим количеством объектов и большей шириной.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для поиска пирамиды максимальной высоты
// из заданной ширины объекта.
#include<bits/stdc++.h>

using namespace std;

  
// Возвращает максимальное количество пирамидальных уровней
// n блоков заданной ширины.

int maxLevel(int boxes[], int n)

{

    // Сортировка объектов в порядке увеличения ширины

    sort(boxes, boxes + n);

  

    int ans = 1;  // Инициализировать результат

  

    // Общая ширина предыдущего уровня и общая

    // количество объектов на предыдущем уровне

    int prev_width = boxes[0];

    int prev_count = 1;

  

    // Номер объекта на текущем уровне.

    int curr_count = 0;

  

    // Ширина текущего уровня.

    int curr_width = 0;

    for (int i=1; i<n; i++)

    {

        // Выбор объекта. Так увеличивай ток

        // ширина и номер объекта.

        curr_width += boxes[i];

        curr_count += 1;

  

        // Если текущая ширина и номер объекта

        // больше предыдущего.

        if (curr_width > prev_width &&

            curr_count > prev_count)

        {

            // Обновляем предыдущую ширину, номер

            // объект на предыдущем уровне.

            prev_width = curr_width;

            prev_count = curr_count;

  

            // Сбрасываем ширину текущего уровня, номер

            // объекта на текущем уровне.

            curr_count = 0;

            curr_width = 0;

  

            // Увеличиваем номер уровня.

            ans++;

        }

    }

  

    return ans;

}

  
// Программа для водителя

int main()

{

    int boxes[] = {10, 20, 30, 50, 60, 70};

    int n = sizeof(boxes)/sizeof(boxes[0]);

    cout << maxLevel(boxes, n) << endl;

    return 0;

}

Джава

// Java-программа для поиска пирамиды максимальной высоты
// из заданной ширины объекта.

import java.io.*;

import java.util.Arrays;

  

class GFG {

      

    // Возвращает максимальное количество пирамидальных

    // выравнивает n блоков заданной ширины.

    static int maxLevel(int []boxes, int n)

    {

  

        // Сортировка объектов в порядке возрастания

        // ширины

        Arrays.sort(boxes);

      

        int ans = 1; // Инициализировать результат

      

        // Общая ширина предыдущего уровня

        // и общее количество объектов в

        // предыдущий уровень

        int prev_width = boxes[0];

        int prev_count = 1;

      

        // Номер объекта в текущем

        // уровень.

        int curr_count = 0;

      

        // Ширина текущего уровня.

        int curr_width = 0;

        for (int i = 1; i < n; i++)

        {

            // Выбор объекта. Так

            // увеличиваем текущую ширину

            // и номер объекта.

            curr_width += boxes[i];

            curr_count += 1;

      

            // Если текущая ширина и

            // номер объекта

            // больше предыдущего.

            if (curr_width > prev_width &&

                curr_count > prev_count)

            {

                  

                // Обновить предыдущую ширину,

                // номер объекта на

                // предыдущий уровень.

                prev_width = curr_width;

                prev_count = curr_count;

      

                // Сбрасываем ширину тока

                // уровень, номер объекта

                // на текущем уровне.

                curr_count = 0;

                curr_width = 0;

      

                // Увеличиваем число

                // уровень.

                ans++;

            }

        }

      

        return ans;

    }

      

    // Программа для водителя

    static public void main (String[] args)

    {

        int []boxes = {10, 20, 30, 50, 60, 70};

        int n = boxes.length;

        System.out.println(maxLevel(boxes, n));

    }

}

  
// Этот код предоставлен anuj_67.

Python 3

# Python 3 программа для поиска
# максимальная высота пирамиды от
# заданная ширина объекта.

  
# Возвращает максимальное количество
количество пирамидальных уровней n
# коробки заданной ширины.

def maxLevel(boxes, n):

      

    # Сортировка объектов по возрастанию

    # порядок ширины

    boxes.sort()

  

    ans = 1 # Инициализировать результат

  

    # Общая ширина предыдущего

    # уровень и общее количество

    # объектов на предыдущем уровне

    prev_width = boxes[0]

    prev_count = 1

  

    # Номер объекта в

    # текущий уровень.

    curr_count = 0

  

    # Ширина текущего уровня.

    curr_width = 0

    for i in range(1, n):

  

        # Подбор объекта. Так

        # увеличить текущую ширину

        № и номер объекта.

        curr_width += boxes[i]

        curr_count += 1

  

        # Если текущая ширина и

        # номер объекта

        # больше, чем предыдущий.

        if (curr_width > prev_width and

            curr_count > prev_count):

  

            # Обновить предыдущую ширину,

            # номер объекта на

            # предыдущий уровень.

            prev_width = curr_width

            prev_count = curr_count

  

            # Сбросить ширину тока

            # уровень, номер объекта

            # на текущем уровне.

            curr_count = 0

            curr_width = 0

  

            # Увеличение номера уровня.

            ans += 1

    return ans

  
Код водителя

if __name__ == "__main__":

    boxes= [10, 20, 30, 50, 60, 70]

    n = len(boxes)

    print(maxLevel(boxes, n))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для поиска максимальной высоты пирамиды
// из заданной ширины объекта.

using System;

  

public class GFG {

      

    // Возвращает максимальное количество пирамидальных

    // выравнивает n блоков заданной ширины.

    static int maxLevel(int []boxes, int n)

    {

        // Сортировка объектов в порядке возрастания

        // ширины

        Array.Sort(boxes);

      

        int ans = 1; // Инициализировать результат

      

        // Общая ширина предыдущего уровня

        // и общее количество объектов в

        // предыдущий уровень

        int prev_width = boxes[0];

        int prev_count = 1;

      

        // Номер объекта в текущем

        // уровень.

        int curr_count = 0;

      

        // Ширина текущего уровня.

        int curr_width = 0;

        for (int i=1; i<n; i++)

        {

            // Выбор объекта. Так

            // увеличиваем текущую ширину

            // и номер объекта.

            curr_width += boxes[i];

            curr_count += 1;

      

            // Если текущая ширина и

            // номер объекта

            // больше предыдущего.

            if (curr_width > prev_width &&

                   curr_count > prev_count)

            {

                  

                // Обновить предыдущую ширину,

                // номер объекта на

                // предыдущий уровень.

                prev_width = curr_width;

                prev_count = curr_count;

      

                // Сбрасываем ширину тока

                // уровень, номер объекта

                // на текущем уровне.

                curr_count = 0;

                curr_width = 0;

      

                // Увеличиваем число

                // уровень.

                ans++;

            }

        }

      

        return ans;

    }

      

    // Программа для водителя

    static public void Main ()

    {

        int []boxes = {10, 20, 30, 50, 60, 70};

        int n = boxes.Length;

        Console.WriteLine(maxLevel(boxes, n));

    }

}

  
// Этот код предоставлен anuj_67.

PHP

<?php
// PHP программа для поиска максимума
// высота пирамиды от
// заданная ширина объекта.

  
// Возвращает максимальное количество
// пирамидальные уровни n ящиков
// заданной ширины.

function maxLevel($boxes, $n)

{

    // Сортировка объектов по возрастанию

    // порядок ширин

    sort($boxes);

  

    // Инициализировать результат

    $ans = 1; 

  

    // Общая ширина предыдущего

    // уровень и общее количество

    // объектов предыдущего уровня

    $prev_width = $boxes[0];

    $prev_count = 1;

  

    // Номер объекта

    // на текущем уровне.

    $curr_count = 0;

  

    // Ширина текущего уровня.

    $curr_width = 0;

    for ( $i = 1; $i < $n; $i++)

    {

        // Выбор объекта. Так

        // увеличиваем текущую ширину

        // и номер объекта.

        $curr_width += $boxes[$i];

        $curr_count += 1;

  

        // Если текущая ширина и номер

        // объекта больше

        // чем предыдущий.

        if ($curr_width > $prev_width and

            $curr_count > $prev_count)

        {

            // Обновляем предыдущую ширину, номер

            // объекта на предыдущем уровне.

            $prev_width = $curr_width;

            $prev_count = $curr_count;

  

            // Сбрасываем ширину тока

            // уровень, номер объекта

            // на текущем уровне.

            $curr_count = 0;

            $curr_width = 0;

  

            // Увеличиваем номер уровня.

            $ans++;

        }

    }

    return $ans;

}

  
// Код драйвера

$boxes = array(10, 20, 30, 50, 60, 70);

$n = count($boxes);

echo maxLevel($boxes, $n) ;

  
// Этот код предоставлен anuj_67.
?>


Выход :

3

Сложность времени: O (n log n).

Пожалуйста, смотрите статью ниже для более эффективных решений.
Максимальная высота треугольного расположения значений массива

Эта статья предоставлена Anuj Chauhan . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти максимальную высоту пирамиды из заданного массива объектов

0.00 (0%) 0 votes