Hay n cuerdas de diferentes longitudes, necesitamos conectar estas cuerdas en una cuerda. El costo de conectar dos cuerdas es igual a la suma de sus longitudes. Necesitamos conectar las cuerdas con un costo mínimo.
Por ejemplo, si nos dan 4 cuerdas de longitudes 4, 3, 2 y 6. Podemos conectar las cuerdas de las siguientes maneras.
- Primero, conecta cuerdas de longitudes 2 y 3. Ahora tenemos tres cuerdas de longitudes 4, 6 y 5.
- Ahora conecte cuerdas de longitudes 4 y 5. Ahora tenemos dos cuerdas de longitudes 6 y 9.
- Finalmente conecte las dos cuerdas y todas las cuerdas se habrán conectado.
El costo total para conectar todas las cuerdas es 5 + 9 + 15 = 29. Este es el costo optimizado para conectar las cuerdas. Otras formas de conectar cuerdas siempre tendrían el mismo o más costo. Por ejemplo, si primero conectamos 4 y 6 (obtenemos tres strings de 3, 2 y 10), luego conectamos 10 y 3 (obtenemos dos strings de 13 y 2). Finalmente, conectamos 13 y 2. El costo total de esta manera es 10 + 13 + 15 = 38.
Le recomendamos encarecidamente que haga clic aquí y lo practique antes de pasar a la solución.
Solución:
Si observamos de cerca el problema anterior, podemos notar que las longitudes de las cuerdas que se recogen primero se incluyen más de una vez en el costo total. Por lo tanto, la idea es conectar primero las dos cuerdas más pequeñas y repetir para las cuerdas restantes. Este enfoque es similar a la codificación Huffman . Colocamos las cuerdas más pequeñas en el árbol para que se puedan repetir varias veces en lugar de las cuerdas más largas.
Entonces forma una estructura como un árbol:
La suma contiene la suma de la profundidad de cada valor. Para el arreglo (2, 3, 4, 6) la suma es igual a 2 * 3 + 3 * 3 + 4 * 2 + 6 * 1 = 29 (Según el diagrama).
Algoritmo:
- Cree un montón mínimo e inserte todas las longitudes en el montón mínimo.
- Haga lo siguiente mientras el número de elementos en min-heap no sea uno.
- Extraiga el mínimo y el segundo mínimo de min-heap
- Agregue los dos valores extraídos anteriores e inserte el valor agregado en el montón mínimo.
- Mantenga una variable para el costo total y siga incrementándola por la suma de los valores extraídos.
- Devuelva el valor de este costo total.
A continuación se muestra la implementación del algoritmo anterior.
C++
// C++ program for connecting
// n ropes with minimum cost
#include <bits/stdc++.h>
using namespace std;
// A Min Heap: Collection of min heap nodes
struct MinHeap {
unsigned size; // Current size of min heap
unsigned capacity; // capacity of min heap
int* harr; // Array of minheap nodes
};
// A utility function to create
// a min-heap of a given capacity
struct MinHeap* createMinHeap(unsigned capacity)
{
struct MinHeap* minHeap = new MinHeap;
minHeap->size = 0; // current size is 0
minHeap->capacity = capacity;
minHeap->harr = new int[capacity];
return minHeap;
}
// A utility function to swap two min heap nodes
void swapMinHeapNode(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
// The standard minHeapify function.
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);
}
}
// A utility function to check
// if size of heap is 1 or not
int isSizeOne(struct MinHeap* minHeap)
{
return (minHeap->size == 1);
}
// A standard function to extract
// minimum value node from heap
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;
}
// A utility function to insert
// a new node to 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;
}
// A standard function to build min-heap
void buildMinHeap(struct MinHeap* minHeap)
{
int n = minHeap->size - 1;
int i;
for (i = (n - 1) / 2; i >= 0; --i)
minHeapify(minHeap, i);
}
// Creates a min-heap of capacity
// equal to size and inserts all values
// from len[] in it. Initially, size
// of min heap is equal to capacity
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;
}
// The main function that returns
// the minimum cost to connect n
// ropes of lengths stored in len[0..n-1]
int minCost(int len[], int n)
{
int cost = 0; // Initialize result
// Create a min heap of capacity
// equal to n and put all ropes in it
struct MinHeap* minHeap = createAndBuildMinHeap(len, n);
// Iterate while size of heap doesn't become 1
while (!isSizeOne(minHeap)) {
// Extract two minimum length
// ropes from min heap
int min = extractMin(minHeap);
int sec_min = extractMin(minHeap);
cost += (min + sec_min); // Update total cost
// Insert a new rope in min heap
// with length equal to sum
// of two extracted minimum lengths
insertMinHeap(minHeap, min + sec_min);
}
// Finally return total minimum
// cost for connecting all ropes
return cost;
}
// Driver program to test above functions
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
// Java program to connect n
// ropes with minimum cost
// A class for Min Heap
class MinHeap {
int[] harr; // Array of elements in heap
int heap_size; // Current number of elements in min heap
int capacity; // maximum possible size of min heap
// Constructor: Builds a heap from
// a given array a[] of given size
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--;
}
}
// A recursive method to heapify a subtree
// with the root at given index
// This method assumes that the subtrees
// are already heapified
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; }
// to get index of left child of node at index i
int left(int i) { return (2 * i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2 * i + 2); }
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size <= 0)
return Integer.MAX_VALUE;
if (heap_size == 1) {
heap_size--;
return harr[0];
}
// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size - 1];
heap_size--;
MinHeapify(0);
return root;
}
// Inserts a new key 'k'
void insertKey(int k)
{
if (heap_size == capacity) {
System.out.println("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// A utility function to check
// if size of heap is 1 or not
boolean isSizeOne()
{
return (heap_size == 1);
}
// A utility function to swap two elements
void swap(int x, int y)
{
int temp = harr[x];
harr[x] = harr[y];
harr[y] = temp;
}
// The main function that returns the
// minimum cost to connect n ropes of
// lengths stored in len[0..n-1]
static int minCost(int len[], int n)
{
int cost = 0; // Initialize result
// Create a min heap of capacity equal
// to n and put all ropes in it
MinHeap minHeap = new MinHeap(len, n);
// Iterate while size of heap doesn't become 1
while (!minHeap.isSizeOne()) {
// Extract two minimum length ropes from min heap
int min = minHeap.extractMin();
int sec_min = minHeap.extractMin();
cost += (min + sec_min); // Update total cost
// Insert a new rope in min heap with length equal to sum
// of two extracted minimum lengths
minHeap.insertKey(min + sec_min);
}
// Finally return total minimum
// cost for connecting all ropes
return cost;
}
// Driver code
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));
}
};
// This code is contributed by shubham96301
C#
// C# program to connect n ropes with minimum cost
using System;
// A class for Min Heap
class MinHeap {
int[] harr; // Array of elements in heap
int heap_size; // Current number of elements in min heap
int capacity; // maximum possible size of min heap
// Constructor: Builds a heap from
// a given array a[] of given size
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--;
}
}
// A recursive method to heapify a subtree
// with the root at given index
// This method assumes that the subtrees
// are already heapified
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; }
// to get index of left child of node at index i
int left(int i) { return (2 * i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2 * i + 2); }
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size <= 0)
return int.MaxValue;
if (heap_size == 1) {
heap_size--;
return harr[0];
}
// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size - 1];
heap_size--;
MinHeapify(0);
return root;
}
// Inserts a new key 'k'
void insertKey(int k)
{
if (heap_size == capacity) {
Console.WriteLine("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// A utility function to check
// if size of heap is 1 or not
Boolean isSizeOne()
{
return (heap_size == 1);
}
// A utility function to swap two elements
void swap(int x, int y)
{
int temp = harr[x];
harr[x] = harr[y];
harr[y] = temp;
}
// The main function that returns the
// minimum cost to connect n ropes of
// lengths stored in len[0..n-1]
static int minCost(int[] len, int n)
{
int cost = 0; // Initialize result
// Create a min heap of capacity equal
// to n and put all ropes in it
MinHeap minHeap = new MinHeap(len, n);
// Iterate while size of heap doesn't become 1
while (!minHeap.isSizeOne()) {
// Extract two minimum length ropes from min heap
int min = minHeap.extractMin();
int sec_min = minHeap.extractMin();
cost += (min + sec_min); // Update total cost
// Insert a new rope in min heap with length equal to sum
// of two extracted minimum lengths
minHeap.insertKey(min + sec_min);
}
// Finally return total minimum
// cost for connecting all ropes
return cost;
}
// Driver code
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));
}
};
// This code is contributed by Arnab Kundu
Producción
Total cost for connecting ropes is 29
Análisis de Complejidad:
- Complejidad de tiempo: O(nLogn), asumiendo que usamos un algoritmo de clasificación O(nLogn). Tenga en cuenta que las operaciones de montón como insertar y extraer toman tiempo O (Iniciar sesión).
- Complejidad auxiliar: O (n), el espacio requerido para almacenar los valores en el montón mínimo
Paradigma algorítmico: Algoritmo codicioso
Una implementación simple con STL en C++:
Esto usa la cola de prioridad disponible en STL. Gracias a Pango89 por proporcionar el siguiente código. El enfoque y el algoritmo siguen siendo los mismos. El montón mínimo se reemplaza por una cola de prioridad.
C++
#include <bits/stdc++.h>
using namespace std;
int minCost(int arr[], int n)
{
// Create a priority queue
// https:// www.geeksforgeeks.org/priority-queue-in-cpp-stl/
// By default 'less' is used which is for decreasing order
// and 'greater' is used for increasing order
priority_queue<int, vector<int>, greater<int> > pq(arr, arr + n);
// Initialize result
int res = 0;
// While size of priority queue is more than 1
while (pq.size() > 1) {
// Extract shortest two ropes from pq
int first = pq.top();
pq.pop();
int second = pq.top();
pq.pop();
// Connect the ropes: update result and
// insert the new rope to pq
res += first + second;
pq.push(first + second);
}
return res;
}
// Driver program to test above function
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
// Java program to connect n
// ropes with minimum cost
import java.util.*;
class ConnectRopes {
static int minCost(int arr[], int n)
{
// Create a priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// Adding items to the pQueue
for (int i = 0; i < n; i++) {
pq.add(arr[i]);
}
// Initialize result
int res = 0;
// While size of priority queue
// is more than 1
while (pq.size() > 1) {
// Extract shortest two ropes from pq
int first = pq.poll();
int second = pq.poll();
// Connect the ropes: update result
// and insert the new rope to pq
res += first + second;
pq.add(first + second);
}
return res;
}
// Driver program to test above function
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));
}
}
// This code is contributed by yash_pec
Python3
# Python3 program to connect n
# ropes with minimum cost
import heapq
def minCost(arr, n):
# Create a priority queue out of the
# given list
heapq.heapify(arr)
# Initialize result
res = 0
# While size of priority queue
# is more than 1
while(len(arr) > 1):
# Extract shortest two ropes from arr
first = heapq.heappop(arr)
second = heapq.heappop(arr)
#Connect the ropes: update result
# and insert the new rope to arr
res += first + second
heapq.heappush(arr, first + second)
return res
# Driver code
if __name__ == '__main__':
lengths = [ 4, 3, 2, 6 ]
size = len(lengths)
print("Total cost for connecting ropes is " +
str(minCost(lengths, size)))
# This code is contributed by shivampatel5
C#
// C# program to connect n
// ropes with minimum cost
using System;
using System.Collections.Generic;
public class ConnectRopes
{
static int minCost(int []arr, int n)
{
// Create a priority queue
List<int> pq = new List<int>();
// Adding items to the pQueue
for (int i = 0; i < n; i++)
{
pq.Add(arr[i]);
}
// Initialize result
int res = 0;
// While size of priority queue
// is more than 1
while (pq.Count > 1)
{
pq.Sort();
// Extract shortest two ropes from pq
int first = pq[0];
int second = pq[1];
pq.RemoveRange(0, 2);
// Connect the ropes: update result
// and insert the new rope to pq
res += first + second;
pq.Add(first + second);
}
return res;
}
// Driver program to test above function
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));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program to connect n
// ropes with minimum cost
function minCost(arr,n)
{
// Create a priority queue
let pq = [];
// Adding items to the pQueue
for (let i = 0; i < n; i++) {
pq.push(arr[i]);
}
pq.sort(function(a,b){return a-b;});
// Initialize result
let res = 0;
// While size of priority queue
// is more than 1
while (pq.length > 1) {
// Extract shortest two ropes from pq
let first = pq.shift();
let second = pq.shift();
// Connect the ropes: update result
// and insert the new rope to pq
res += first + second;
pq.push(first + second);
pq.sort(function(a,b){return a-b;});
}
return res;
}
// Driver program to test above function
let len = [4, 3, 2, 6];
let size = len.length;
document.write("Total cost for connecting"
+ " ropes is " + minCost(len, size));
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Total cost for connecting ropes is 29
Análisis de Complejidad:
- Complejidad de tiempo: O(nLogn), asumiendo que usamos un algoritmo de clasificación O(nLogn).
Tenga en cuenta que las operaciones de montón como insertar y extraer toman tiempo O (Iniciar sesión). - Complejidad auxiliar: O(n).
El espacio requerido para almacenar los valores en el montón mínimo
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA