Dado un número entero N , la tarea es encontrar el costo mínimo para combinar todos los números del 1 al N , donde el costo de combinar dos conjuntos de números A y B es igual al producto del producto de los números en los conjuntos respectivos.
Ejemplos:
Entrada: N = 4
Salida: 32
Fusionar {1} y {2} cuesta 1 * 2 = 2
Fusionar {1, 2} y {3} cuesta 2 * 3 = 6
Fusionar {1, 2, 3} y {4} cuesta 6 * 4 = 24
Por lo tanto, el costo mínimo es 2 + 6 + 24 = 32Entrada: N = 2
Salida: 2
Acercarse:
- El primer enfoque que viene a nuestra mente es la clasificación . Tomamos los dos primeros elementos más pequeños y los agregamos, luego continuamos agregando el resto de los elementos en la array ordenada. Pero falla cuando la suma acumulada actual excede el siguiente valor más pequeño en la array que viene a continuación.
Take N = 5,
If we take the sorting approach, then-
Merge {1} and {2} - 1 * 2 = 2
Merge {1, 2} and {3} - 2 * 3 = 6
Merge{1, 2, 3} and {4} - 6 * 4 = 24
Merge{1, 2, 3, 4} and {5} - 24 * 5 = 120
Total sum = 152
But optimal way is,
Merge {1} and {2} - 1 * 2 = 2
Merge {1, 2} and {3} - 2 * 3 = 6
Merge {4} and {5} - 4 * 5 = 20
Merge {1, 2, 3} and {4, 5} - 6 * 20 = 120
Total sum = 148
This is the minimal answer.
- Por lo tanto, el enfoque correcto para resolver este problema es el enfoque basado en Min-heap . Inicialmente, empujamos todos los números del 1 al N en el Min-Heap.
- En cada iteración, extraemos el mínimo y el segundo elemento mínimo del Min-Heap e insertamos su producto nuevamente en él. Esto asegura que el costo adicional generado será mínimo .
- Seguimos repitiendo el paso anterior hasta que solo quede un elemento en el Min-Heap. La suma calculada hasta ese instante nos da la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the Minimum
// cost to merge numbers
// from 1 to N.
#include <bits/stdc++.h>
using namespace std;
// Function returns the
// minimum cost
int GetMinCost(int N)
{
// Min Heap representation
priority_queue<int, vector<int>,
greater<int> > pq;
// Add all elements to heap
for (int i = 1; i <= N; i++) {
pq.push(i);
}
int cost = 0;
while (pq.size() > 1)
{
// First minimum
int mini = pq.top();
pq.pop();
// Second minimum
int secondmini = pq.top();
pq.pop();
// Multiply them
int current = mini * secondmini;
// Add to the cost
cost += current;
// Push the product into the
// heap again
pq.push(current);
}
// Return the optimal cost
return cost;
}
// Driver code
int main()
{
int N = 5;
cout << GetMinCost(N);
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function returns the
// minimum cost
static int GetMinCost(int N)
{
// Min Heap representation
PriorityQueue<Integer> pq;
pq = new PriorityQueue<>();
// Add all elements to heap
for(int i = 1; i <= N; i++)
{
pq.add(i);
}
int cost = 0;
while (pq.size() > 1)
{
// First minimum
int mini = pq.remove();
// Second minimum
int secondmini = pq.remove();
// Multiply them
int current = mini * secondmini;
// Add to the cost
cost += current;
// Push the product into the
// heap again
pq.add(current);
}
// Return the optimal cost
return cost;
}
// Driver Code
public static void main(String args[])
{
int N = 5;
// Function call
System.out.println(GetMinCost(N));
}
}
// This code is contributed by rutvik_56
Python3
# python3 program to find the Minimum # cost to merge numbers # from 1 to N. # Function returns the # minimum cost def GetMinCost(N): # Min Heap representation pq = [] # Add all elements to heap for i in range(1, N+1, 1): pq.append(i) pq.sort(reverse = False) cost = 0 while (len(pq) > 1): # First minimum mini = pq[0] pq.remove(pq[0]) # Second minimum secondmini = pq[0] pq.remove(pq[0]) # Multiply them current = mini * secondmini # Add to the cost cost += current # Push the product into the # heap again pq.append(current) pq.sort(reverse = False) # Return the optimal cost return cost # Driver code if __name__ == '__main__': N = 5 print(GetMinCost(N)) # This code is contributed by Bhupendra_Singh
C#
// C# program to find the Minimum
// cost to merge numbers
// from 1 to N.
using System;
using System.Collections.Generic;
class GFG{
// Function returns the
// minimum cost
static int GetMinCost(int N)
{
// Min Heap representation
List<int> pq = new List<int>();
// Add all elements to heap
for(int i = 1; i <= N; i++)
{
pq.Add(i);
}
int cost = 0;
pq.Sort();
while (pq.Count > 1)
{
// First minimum
int mini = pq[0];
pq.RemoveAt(0);
// Second minimum
int secondmini = pq[0];
pq.RemoveAt(0);
// Multiply them
int current = mini * secondmini;
// Add to the cost
cost += current;
// Push the product into the
// heap again
pq.Add(current);
pq.Sort();
}
// Return the optimal cost
return cost;
}
// Driver code
static void Main()
{
int N = 5;
Console.WriteLine(GetMinCost(N));
}
}
// This code is contributed by divyeshrabadiya07
Javascript
<script>
// Javascript program for the above approach
// Function returns the
// minimum cost
function GetMinCost(N)
{
// Min Heap representation
let pq = [];
// Add all elements to heap
for(let i = 1; i <= N; i++)
{
pq.push(i);
}
pq.sort(function(a, b){return a - b});
let cost = 0;
while (pq.length > 1)
{
// First minimum
let mini = pq[0];
pq.shift();
// Second minimum
let secondmini = pq[0];
pq.shift();
// Multiply them
let current = mini * secondmini;
// Add to the cost
cost += current;
// Push the product into the
// heap again
pq.push(current);
pq.sort(function(a, b){return a - b});
}
// Return the optimal cost
return cost;
}
let N = 5;
// Function call
document.write(GetMinCost(N));
// This code is contributed by decode2207.
</script>
Producción:
148
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por VikasVishwakarma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA