Рубрики

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

Там даны n веревок разной длины, нам нужно соединить эти веревки в одну веревку. Стоимость соединения двух веревок равна сумме их длин. Нам нужно соединить веревки с минимальными затратами.

Например, если нам дано 4 веревки длиной 4, 3, 2 и 6. Мы можем соединить веревки следующими способами.
1) Сначала соедините веревки длиной 2 и 3. Теперь у нас есть три веревки длиной 4, 6 и 5.
2) Теперь соедините веревки длиной 4 и 5. Теперь у нас есть две веревки длиной 6 и 9.
3) Наконец соедините две веревки, и все веревки соединились.

Общая стоимость соединения всех канатов составляет 5 + 9 + 15 = 29. Это оптимизированная стоимость для соединения канатов. Другие способы соединения веревок всегда будут иметь одинаковую или более высокую стоимость. Например, если мы сначала соединяем 4 и 6 (мы получаем три строки 3, 2 и 10), то соединяем 10 и 3 (мы получаем две строки 13 и 2). Наконец, мы соединяем 13 и 2. Общая стоимость таким образом составляет 10 + 13 + 15 = 38.

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

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

Ниже приведен полный алгоритм поиска минимальной стоимости подключения n веревок.
Пусть в массиве len будет храниться n веревок длин [0..n-1]
1) Создайте минимальную кучу и вставьте все длины в минимальную кучу.
2) Выполните следующие действия, пока количество элементов в куче мин не одно.
…… а) Извлечь минимум и второй минимум из минимальной кучи
…… б) Добавьте вышеупомянутые два извлеченных значения и вставьте добавленное значение в минимальную кучу.
… C) Поддерживайте переменную для общих затрат и продолжайте увеличивать ее на сумму извлеченных значений.
3) Верните значение этой общей стоимости.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для соединения n веревок с минимальными затратами
#include <iostream>

  

using namespace std;

  
// Min Heap: Коллекция узлов min heap

struct MinHeap {

    unsigned size; // Текущий размер кучи мин

    unsigned capacity; // емкость мин кучи

    int* harr; // Присоединение узлов minheap

};

  
// Утилита для создания минимальной кучи заданной емкости

struct MinHeap* createMinHeap(unsigned capacity)

{

    struct MinHeap* minHeap = new MinHeap;

    minHeap->size = 0; // текущий размер равен 0

    minHeap->capacity = capacity;

    minHeap->harr = new int[capacity];

    return minHeap;

}

  
// Вспомогательная функция для замены двух минимальных узлов кучи

void swapMinHeapNode(int* a, int* b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

  
// Стандартная функция minHeapify.

void minHeapify(struct MinHeap* minHeap, int idx)

{

    int smallest = idx;

    int left = 2 * idx + 1;

    int right = 2 * idx + 2;

  

    if (left < minHeap->size && minHeap->harr[left] < minHeap->harr[smallest])

        smallest = left;

  

    if (right < minHeap->size && minHeap->harr[right] < minHeap->harr[smallest])

        smallest = right;

  

    if (smallest != idx) {

        swapMinHeapNode(&minHeap->harr[smallest], &minHeap->harr[idx]);

        minHeapify(minHeap, smallest);

    }

}

  
// Утилита для проверки, если размер кучи равен 1 или нет

int isSizeOne(struct MinHeap* minHeap)

{

    return (minHeap->size == 1);

}

  
// Стандартная функция для извлечения узла минимального значения из кучи

int extractMin(struct MinHeap* minHeap)

{

    int temp = minHeap->harr[0];

    minHeap->harr[0] = minHeap->harr[minHeap->size - 1];

    --minHeap->size;

    minHeapify(minHeap, 0);

    return temp;

}

  
// Вспомогательная функция для вставки нового узла в Min Heap

void insertMinHeap(struct MinHeap* minHeap, int val)

{

    ++minHeap->size;

    int i = minHeap->size - 1;

    while (i && (val < minHeap->harr[(i - 1) / 2])) {

        minHeap->harr[i] = minHeap->harr[(i - 1) / 2];

        i = (i - 1) / 2;

    }

    minHeap->harr[i] = val;

}

  
// Стандартная функция для построения минимальной кучи

void buildMinHeap(struct MinHeap* minHeap)

{

    int n = minHeap->size - 1;

    int i;

    for (i = (n - 1) / 2; i >= 0; --i)

        minHeapify(minHeap, i);

}

  
// Создаем минимальную кучу емкости, равную размеру, и вставляем все значения
// из len [] в нем. Первоначально размер минимальной кучи равен емкости

struct MinHeap* createAndBuildMinHeap(int len[], int size)

{

    struct MinHeap* minHeap = createMinHeap(size);

    for (int i = 0; i < size; ++i)

        minHeap->harr[i] = len[i];

    minHeap->size = size;

    buildMinHeap(minHeap);

    return minHeap;

}

  
// Основная функция, которая возвращает минимальную стоимость для подключения n веревок
// длины сохраняются в len [0..n-1]

int minCost(int len[], int n)

{

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

  

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

    struct MinHeap* minHeap = createAndBuildMinHeap(len, n);

  

    // Итерация, пока размер кучи не становится 1

    while (!isSizeOne(minHeap)) {

        // Извлекаем две веревки минимальной длины из минимальной кучи

        int min = extractMin(minHeap);

        int sec_min = extractMin(minHeap);

  

        cost += (min + sec_min); // Обновить общую стоимость

  

        // Вставляем новую веревку в кучу мин с длиной, равной сумме

        // из двух извлеченных минимальных длин

        insertMinHeap(minHeap, min + sec_min);

    }

  

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

    return cost;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int len[] = { 4, 3, 2, 6 };

    int size = sizeof(len) / sizeof(len[0]);

    cout << "Total cost for connecting ropes is " << minCost(len, size);

    return 0;

}

Джава

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

  
// Класс для Min Heap

class MinHeap {

    int[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

    int capacity; // максимально возможный размер кучи min

  

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(int a[], int size)

    {

        heap_size = size;

        capacity = size;

        harr = a;

        int i = (heap_size - 1) / 2;

        while (i >= 0) {

            MinHeapify(i);

            i--;

        }

    }

  

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // Этот метод предполагает, что поддеревья

    // уже куча

    void MinHeapify(int i)

    {

        int l = left(i);

        int r = right(i);

        int smallest = i;

        if (l < heap_size && harr[l] < harr[i])

            smallest = l;

        if (r < heap_size && harr[r] < harr[smallest])

            smallest = r;

        if (smallest != i) {

            swap(i, smallest);

            MinHeapify(smallest);

        }

    }

  

    int parent(int i) { return (i - 1) / 2; }

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2 * i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2 * i + 2); }

  

    // Метод удаления минимального элемента (или корня) из минимальной кучи

    int extractMin()

    {

        if (heap_size <= 0)

            return Integer.MAX_VALUE;

        if (heap_size == 1) {

            heap_size--;

            return harr[0];

        }

  

        // Сохраняем минимальное значение и удаляем его из кучи

        int root = harr[0];

        harr[0] = harr[heap_size - 1];

        heap_size--;

        MinHeapify(0);

  

        return root;

    }

  

    // Вставляем новый ключ 'k'

    void insertKey(int k)

    {

        if (heap_size == capacity) {

            System.out.println("Overflow: Could not insertKey");

            return;

        }

  

        // Сначала вставляем новый ключ в конце

        heap_size++;

        int i = heap_size - 1;

        harr[i] = k;

  

        // Исправляем свойство min heap, если оно нарушено

        while (i != 0 && harr[parent(i)] > harr[i]) {

            swap(i, parent(i));

            i = parent(i);

        }

    }

  

    // Полезная функция для проверки

    // если размер кучи равен 1 или нет

    boolean isSizeOne()

    {

        return (heap_size == 1);

    }

  

    // Утилита для замены двух элементов

    void swap(int x, int y)

    {

        int temp = harr[x];

        harr[x] = harr[y];

        harr[y] = temp;

    }

  

    // Основная функция, которая возвращает

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

    // длины сохраняются в len [0..n-1]

    static int minCost(int len[], int n)

    {

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

  

        // Создание минимальной кучи емкости, равной

        // и положить все веревки в нем

        MinHeap minHeap = new MinHeap(len, n);

  

        // Итерация, пока размер кучи не становится 1

        while (!minHeap.isSizeOne()) {

            // Извлекаем две веревки минимальной длины из минимальной кучи

            int min = minHeap.extractMin();

            int sec_min = minHeap.extractMin();

  

            cost += (min + sec_min); // Обновить общую стоимость

  

            // Вставляем новую веревку в кучу мин с длиной, равной сумме

            // из двух извлеченных минимальных длин

            minHeap.insertKey(min + sec_min);

        }

  

        // Наконец возвращаем общий минимум

        // стоимость подключения всех канатов

        return cost;

    }

  

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

    public static void main(String args[])

    {

        int len[] = { 4, 3, 2, 6 };

        int size = len.length;

  

        System.out.println("Total cost for connecting ropes is " + minCost(len, size));

    }

};

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

C #

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

using System;

  
// Класс для Min Heap

class MinHeap 

    int[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

    int capacity; // максимально возможный размер кучи min

  

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(int []a, int size) 

    

        heap_size = size; 

        capacity = size; 

        harr = a; 

        int i = (heap_size - 1) / 2; 

        while (i >= 0) 

        

            MinHeapify(i); 

            i--; 

        

    

  

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // Этот метод предполагает, что поддеревья

    // уже куча

    void MinHeapify(int i) 

    

        int l = left(i); 

        int r = right(i); 

        int smallest = i; 

        if (l < heap_size && harr[l] < harr[i]) 

            smallest = l; 

        if (r < heap_size && harr[r] < harr[smallest]) 

            smallest = r; 

        if (smallest != i) 

        

            swap(i, smallest); 

            MinHeapify(smallest); 

        

    

  

    int parent(int i) { return (i - 1) / 2; } 

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2 * i + 1); } 

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2 * i + 2); } 

  

    // Метод удаления минимального элемента (или корня) из минимальной кучи

    int extractMin() 

    

        if (heap_size <= 0) 

            return int.MaxValue; 

        if (heap_size == 1) 

        

            heap_size--; 

            return harr[0]; 

        

  

        // Сохраняем минимальное значение и удаляем его из кучи

        int root = harr[0]; 

        harr[0] = harr[heap_size - 1]; 

        heap_size--; 

        MinHeapify(0); 

  

        return root; 

    

  

    // Вставляем новый ключ 'k'

    void insertKey(int k) 

    

        if (heap_size == capacity) 

        

            Console.WriteLine("Overflow: Could not insertKey"); 

            return

        

  

        // Сначала вставляем новый ключ в конце

        heap_size++; 

        int i = heap_size - 1; 

        harr[i] = k; 

  

        // Исправляем свойство min heap, если оно нарушено

        while (i != 0 && harr[parent(i)] > harr[i]) 

        

            swap(i, parent(i)); 

            i = parent(i); 

        

    

  

    // Полезная функция для проверки

    // если размер кучи равен 1 или нет

    Boolean isSizeOne() 

    

        return (heap_size == 1); 

    

  

    // Утилита для замены двух элементов

    void swap(int x, int y) 

    

        int temp = harr[x]; 

        harr[x] = harr[y]; 

        harr[y] = temp; 

    

  

    // Основная функция, которая возвращает

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

    // длины сохраняются в len [0..n-1]

    static int minCost(int []len, int n) 

    

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

  

        // Создание минимальной кучи емкости, равной

        // и положить все веревки в нем

        MinHeap minHeap = new MinHeap(len, n); 

  

        // Итерация, пока размер кучи не становится 1

        while (!minHeap.isSizeOne())

        

            // Извлекаем две веревки минимальной длины из минимальной кучи

            int min = minHeap.extractMin(); 

            int sec_min = minHeap.extractMin(); 

  

            cost += (min + sec_min); // Обновить общую стоимость

  

            // Вставляем новую веревку в кучу мин с длиной, равной сумме

            // из двух извлеченных минимальных длин

            minHeap.insertKey(min + sec_min); 

        

  

        // Наконец возвращаем общий минимум

        // стоимость подключения всех канатов

        return cost; 

    

  

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

    public static void Main(String []args) 

    

        int []len = { 4, 3, 2, 6 }; 

        int size = len.Length; 

  

        Console.WriteLine("Total cost for connecting ropes is "

                                            minCost(len, size)); 

    

}; 

  
// Этот код предоставлен Арнабом Кунду

Выход:

Total cost for connecting ropes is 29

Сложность времени: временная сложность алгоритма равна O (nLogn), если предположить, что мы используем алгоритм сортировки O (nLogn). Обратите внимание, что операции с кучей, такие как вставка и извлечение, занимают O (Logn) время.

Алгоритмическая парадигма: жадный алгоритм

Простая реализация с STL на C ++
Ниже приводится простая реализация, которая использует priority_queue, доступную в STL. Спасибо Pango89 за предоставленный ниже код.

C ++

#include <iostream>
#include <queue>

  

using namespace std;

  

int minCost(int arr[], int n)

{

    // Создать приоритетную очередь ( http: // www.cplusplus.com/reference/queue/priority_queue/)

    // По умолчанию используется «меньше», что для убывания порядка

    // и «больше» используется для увеличения порядка

    priority_queue<int, vector<int>, greater<int> > pq(arr, arr + n);

  

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

    int res = 0;

  

    // размер очереди с приоритетом больше 1

    while (pq.size() > 1) {

        // Извлекаем кратчайшие две веревки из pq

        int first = pq.top();

        pq.pop();

        int second = pq.top();

        pq.pop();

  

        // Соединяем веревки: обновляем результат и

        // вставляем новый трос в pq

        res += first + second;

        pq.push(first + second);

    }

  

    return res;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int len[] = { 4, 3, 2, 6 };

    int size = sizeof(len) / sizeof(len[0]);

    cout << "Total cost for connecting ropes is " << minCost(len, size);

    return 0;

}

Джава

// Java программа для подключения
// веревки с минимальной стоимостью

import java.util.*;

  

class ConnectRopes {

    static int minCost(int arr[], int n)

    {

        // Создать приоритетную очередь

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

  

        // Добавление элементов в pQueue

        for (int i = 0; i < n; i++) {

            pq.add(arr[i]);

        }

  

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

        int res = 0;

  

        // Пока размер очереди приоритета

        // больше 1

        while (pq.size() > 1) {

            // Извлекаем кратчайшие две веревки из pq

            int first = pq.poll();

            int second = pq.poll();

  

            // Соединяем веревки: результат обновления

            // и вставляем новую веревку в pq

            res += first + second;

            pq.add(first + second);

        }

  

        return res;

    }

  

    // Программа драйвера для проверки вышеуказанной функции

    public static void main(String args[])

    {

        int len[] = { 4, 3, 2, 6 };

        int size = len.length;

        System.out.println("Total cost for connecting"

                           + " ropes is " + minCost(len, size));

    }

}
// Этот код предоставлен yash_pec


Выход:

Total cost for connecting ropes is 29

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

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

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

0.00 (0%) 0 votes