Рубрики

Минимальная стоимость нарезки доски на квадраты

Дана доска длиной m и шириной n, нам нужно разбить эту доску на квадраты m * n так, чтобы стоимость взлома была минимальной. стоимость резки для каждого края будет дана для доски. Короче говоря, нам нужно выбрать такую последовательность резки, чтобы затраты были минимальными.
Примеры:



For above board optimal way to cut into square is:
Total minimum cost in above case is 42. It is 
evaluated using following steps.

Initial Value : Total_cost = 0
Total_cost = Total_cost + edge_cost * total_pieces

Cost 4 Horizontal cut         Cost = 0 + 4*1 = 4
Cost 4 Vertical cut        Cost = 4 + 4*2 = 12
Cost 3 Vertical cut        Cost = 12 + 3*2 = 18
Cost 2 Horizontal cut        Cost = 18 + 2*3 = 24
Cost 2 Vertical cut        Cost = 24 + 2*3 = 30
Cost 1 Horizontal cut        Cost = 30 + 1*4 = 34
Cost 1 Vertical cut        Cost = 34 + 1*4 = 38
Cost 1 Vertical cut        Cost = 38 + 1*4 = 42

Эта проблема может быть решена с использованием жадного подхода. Если общая стоимость обозначается как S, то S = a1w1 + a2w2… + akwk, где wi — это стоимость определенного обрезания кромки, а ai — соответствующий коэффициент. Коэффициент ai определяется общей суммой. количество срезов, в которых мы участвовали, используя край в конце процесса резки. Обратите внимание, что сумма коэффициентов всегда постоянна, поэтому мы хотим найти распределение ai, которое можно получить так, чтобы S было минимальным. Чтобы сделать это, мы выполняем нарезки на самом высоком ценовом фронте как можно раньше , что приведет к оптимальному S. Если мы столкнемся с несколькими ребрами, имеющими одинаковую стоимость, мы можем сначала вырезать любой из них.
Ниже приведено решение с использованием вышеуказанного подхода: сначала мы отсортировали затраты на резку по краям в обратном порядке, а затем переключаем их от более высоких затрат к более низким затратам, создавая наше решение. Каждый раз, когда мы выбираем кромку, счетчик деталей увеличивается на 1, что должно быть умножено каждый раз на соответствующую стоимость резки кромки.
Обратите внимание, что ниже использовался метод сортировки, посылая больший () в качестве 3-го аргумента, чтобы метод сортировки сортировал число в порядке возрастания, это предопределенная функция библиотеки.

C ++

// C ++ программа для деления доски на m * n квадратов
#include <bits/stdc++.h>

using namespace std;

  
// метод возвращает минимальную стоимость, чтобы разбить доску
// m * n квадратов

int minimumCostOfBreaking(int X[], int Y[], int m, int n)

{

    int res = 0;

  

    // сортируем горизонтальную стоимость в обратном порядке

    sort(X, X + m, greater<int>());

  

    // сортируем вертикальную стоимость в обратном порядке

    sort(Y, Y + n, greater<int>());

  

    // инициализируем текущую ширину как 1

    int hzntl = 1, vert = 1;

  

    // цикл до обработки одного или обоих массивов затрат

    int i = 0, j = 0;

    while (i < m && j < n)

    {

        if (X[i] > Y[j])

        {

            res += X[i] * vert;

  

            // увеличить текущий горизонтальный счетчик на 1

            hzntl++;

            i++;

        }

        else

        {

            res += Y[j] * hzntl;

  

            // увеличить текущее количество вертикальных частей на 1

            vert++;

            j++;

        }

    }

  

    // цикл для горизонтального массива, если остается

    int total = 0;

    while (i < m)

        total += X[i++];

    res += total * vert;

  

    // цикл для вертикального массива, если остается

    total = 0;

    while (j < n)

        total += Y[j++];

    res += total * hzntl;

  

    return res;

}

  
// Код драйвера для тестирования вышеуказанных методов

int main()

{

    int m = 6, n = 4;

    int X[m-1] = {2, 1, 3, 1, 4};

    int Y[n-1] = {4, 1, 2};

    cout << minimumCostOfBreaking(X, Y, m-1, n-1);

    return 0;

}

Джава

// Java-программа для деления
// доска в m * n квадратов

import java.util.Arrays;

import java.util.Collections;

  

class GFG

{

    // метод возвращает минимальную стоимость, чтобы разбить доску

    // m * n квадратов

    static int minimumCostOfBreaking(Integer X[], Integer Y[], 

                                                 int m, int n)

    {

        int res = 0;

      

        // сортируем горизонтальную стоимость в обратном порядке

        Arrays.sort(X, Collections.reverseOrder());

      

        // сортируем вертикальную стоимость в обратном порядке

        Arrays.sort(Y, Collections.reverseOrder());

      

        // инициализируем текущую ширину как 1

        int hzntl = 1, vert = 1;

      

        // цикл до одного или обоих

        // массив затрат обработан

        int i = 0, j = 0;

        while (i < m && j < n)

        {

            if (X[i] > Y[j])

            {

                res += X[i] * vert;

      

                // увеличиваем текущую горизонталь

                // количество деталей на 1

                hzntl++;

                i++;

            }

            else

            {

                res += Y[j] * hzntl;

      

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

                // количество деталей на 1

                vert++;

                j++;

            }

        }

      

        // цикл для горизонтального массива,

        // если остается

        int total = 0;

        while (i < m)

            total += X[i++];

        res += total * vert;

      

        // цикл для вертикального массива,

        // если остается

        total = 0;

        while (j < n)

            total += Y[j++];

        res += total * hzntl;

      

        return res;

    }

      

    // Драйвер программы

    public static void main(String arg[])

    {

        int m = 6, n = 4;

        Integer X[] = {2, 1, 3, 1, 4};

        Integer Y[] = {4, 1, 2};

        System.out.print(minimumCostOfBreaking(X, Y, m-1, n-1));

    }

}

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

python3

# Python программа для деления доски на m * n квадратов

  
# Метод возвращает минимальную стоимость
# разбить доску на m * n квадратов

def minimumCostOfBreaking(X, Y, m, n):

  

    res = 0

  

    # сортировка горизонтальной стоимости в обратном порядке

    X.sort(reverse = True)

  

    # сортировка вертикальной стоимости в обратном порядке

    Y.sort(reverse = True)

  

    # инициализировать текущую ширину как 1

    hzntl = 1; vert = 1

  

    # цикл до одного или обоих

    # массив затрат обработан

    i = 0; j = 0

    while (i < m and j < n):

      

        if (X[i] > Y[j]):

          

            res += X[i] * vert

  

            # увеличить текущий горизонтальный

            Количество деталей на 1

            hzntl += 1

            i += 1

          

        else:

            res += Y[j] * hzntl

  

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

            Количество деталей на 1

            vert += 1

            j += 1

  

    # цикл для горизонтального массива, если остается

    total = 0

    while (i < m):

        total += X[i]

        i += 1

    res += total * vert

  

    #loop для вертикального массива, если остается

    total = 0

    while (j < n):

        total += Y[j]

        j += 1

    res += total * hzntl

  

    return res

      
# Драйверная программа

m = 6; n = 4

X = [2, 1, 3, 1, 4]

Y = [4, 1, 2]

  

print(minimumCostOfBreaking(X, Y, m-1, n-1))

  

  
# Этот код предоставлен Anant Agarwal.

C #

// C # программа для деления
// доска в m * n квадратов

using System; 

  

class GFG 

    // метод возвращает минимальную стоимость, чтобы разбить доску

    // m * n квадратов

    static int minimumCostOfBreaking(int[] X, int[] Y, 

                                        int m, int n) 

    

        int res = 0; 

      

        // сортируем горизонтальную стоимость в обратном порядке

        Array.Sort<int>(X, new Comparison<int>( 

                (i1, i2) => i2.CompareTo(i1)));

      

        // сортируем вертикальную стоимость в обратном порядке

        Array.Sort<int>(Y, new Comparison<int>( 

                (i1, i2) => i2.CompareTo(i1)));

      

        // инициализируем текущую ширину как 1

        int hzntl = 1, vert = 1; 

      

        // цикл до одного или обоих

        // массив затрат обработан

        int i = 0, j = 0; 

        while (i < m && j < n) 

        

            if (X[i] > Y[j]) 

            

                res += X[i] * vert; 

      

                // увеличиваем текущую горизонталь

                // количество деталей на 1

                hzntl++; 

                i++; 

            

            else

            

                res += Y[j] * hzntl; 

      

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

                // количество деталей на 1

                vert++; 

                j++; 

            

        

      

        // цикл для горизонтального массива,

        // если остается

        int total = 0; 

        while (i < m) 

            total += X[i++]; 

        res += total * vert; 

      

        // цикл для вертикального массива,

        // если остается

        total = 0; 

        while (j < n) 

            total += Y[j++]; 

        res += total * hzntl; 

      

        return res; 

    

      

    // Драйвер программы

    public static void Main(String []arg) 

    

        int m = 6, n = 4; 

        int []X = {2, 1, 3, 1, 4}; 

        int []Y = {4, 1, 2}; 

        Console.WriteLine(minimumCostOfBreaking(X, Y, m-1, n-1)); 

    

  
// Этот код предоставлен Принчи Сингхом


Выход:

42

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

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

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

Минимальная стоимость нарезки доски на квадраты

0.00 (0%) 0 votes