Dada una array arr[] que consiste en N enteros y un entero K , la tarea es dividir la array dada en K subconjuntos que no se superponen de modo que el máximo entre la suma de todos los subconjuntos sea el mínimo.
Ejemplos:
Entrada: arr[] = {1, 7, 9, 2, 12, 3, 3}, M = 3
Salida: 13
Explicación:
una forma posible de dividir la array en 3 subconjuntos que no se superponen es {arr[4], arr[0]}, {arr[2], arr[6]} y {arr[1], arr[5], arr[3]}.
La suma de cada subconjunto es 13, 12 y 12 respectivamente. Ahora bien, el máximo entre todas las sumas de subconjuntos es 13, que es la mínima suma posible.Entrada: arr[] = {1, 2, 3, 4, 5}, M = 2
Salida: 8
Enfoque: el problema dado puede resolverse mediante el enfoque codicioso utilizando la cola de prioridad y ordenando la array dada .
- Inicialice un Min-Heap usando la cola de prioridad , digamos PQ , para almacenar la suma de los elementos de cada grupo.
- Iterar en el rango [1, K] y empujar 0 en el PQ .
- Ordene la array, arr[] en orden decreciente .
- Recorra la array arr[] y para cada elemento de la array arr[i] , agregue el elemento arr[i] al grupo de suma más pequeño que estará en la parte superior de la cola de prioridad PQ .
- Después de completar los pasos anteriores, imprima el último elemento de la cola de prioridad PQ como la suma máxima minimizada resultante entre todos los grupos posibles.
A continuación se muestra la implementación del enfoque anterior:
++++
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to split the array into M
// groups such that maximum of the sum
// of all elements of all the groups
// is minimized
int findMinimumValue(int arr[], int N,
int M)
{
// Sort the array in decreasing order
sort(arr, arr + N, greater<int>());
// Initialize priority queue (Min heap)
priority_queue<int, vector<int>,
greater<int> >
pq;
// Push 0 for all the M groups
for (int i = 1; i <= M; ++i) {
pq.push(0);
}
// Traverse the array, arr[]
for (int i = 0; i < N; ++i) {
// Pop the group having the
// minimum sum
int val = pq.top();
pq.pop();
// Increment val by arr[i]
val += arr[i];
// Push the new sum of the
// group into the pq
pq.push(val);
}
// Iterate while size of the pq
// is greater than 1
while (pq.size() > 1) {
pq.pop();
}
// Return result
return pq.top();
}
// Driver Code
int main()
{
int arr[] = { 1, 7, 9, 2, 12, 3, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 3;
cout << findMinimumValue(arr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
// Function to split the array into M
// groups such that maximum of the sum
// of all elements of all the groups
// is minimized
static int findMinimumValue(Vector<Integer> arr, int N, int M)
{
// Sort the array in decreasing order
Collections.sort(arr);
Collections.reverse(arr);
// Initialize priority queue (Min heap)
Vector<Integer> pq = new Vector<Integer>();
// Push 0 for all the M groups
for (int i = 1; i <= M; ++i) {
pq.add(0);
}
Collections.sort(pq);
// Traverse the array, arr[]
for (int i = 0; i < N; ++i) {
// Pop the group having the
// minimum sum
int val = pq.get(0);
pq.remove(0);
// Increment val by arr[i]
val += arr.get(i);
// Push the new sum of the
// group into the pq
pq.add(val);
Collections.sort(pq);
}
// Iterate while size of the pq
// is greater than 1
while (pq.size() > 1) {
pq.remove(0);
}
// Return result
return pq.get(0);
}
public static void main(String[] args) {
Integer[] arr = { 1, 7, 9, 2, 12, 3, 3 };
Vector<Integer> Arr = new Vector<Integer>();
Collections.addAll(Arr, arr);
int N = Arr.size();
int K = 3;
System.out.println(findMinimumValue(Arr, N, K));
}
}
// This code is contributed by divyesh072019.
Python3
# Python3 program for the above approach # Function to split the array into M # groups such that maximum of the sum # of all elements of all the groups # is minimized def findMinimumValue(arr, N, M): # Sort the array in decreasing order arr.sort() arr.reverse() # Initialize priority queue (Min heap) pq = [] # Push 0 for all the M groups for i in range(1, M + 1): pq.append(0) pq.sort() # Traverse the array, arr[] for i in range(N): # Pop the group having the # minimum sum val = pq[0] del pq[0] # Increment val by arr[i] val += arr[i] # Push the new sum of the # group into the pq pq.append(val) pq.sort() # Iterate while size of the pq # is greater than 1 while (len(pq) > 1) : del pq[0] # Return result return pq[0] arr = [ 1, 7, 9, 2, 12, 3, 3 ] N = len(arr) K = 3 print(findMinimumValue(arr, N, K)) # This code is contributed by suresh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to split the array into M
// groups such that maximum of the sum
// of all elements of all the groups
// is minimized
static int findMinimumValue(int[] arr, int N, int M)
{
// Sort the array in decreasing order
Array.Sort(arr);
Array.Reverse(arr);
// Initialize priority queue (Min heap)
List<int> pq = new List<int>();
// Push 0 for all the M groups
for (int i = 1; i <= M; ++i) {
pq.Add(0);
}
pq.Sort();
// Traverse the array, arr[]
for (int i = 0; i < N; ++i) {
// Pop the group having the
// minimum sum
int val = pq[0];
pq.RemoveAt(0);
// Increment val by arr[i]
val += arr[i];
// Push the new sum of the
// group into the pq
pq.Add(val);
pq.Sort();
}
// Iterate while size of the pq
// is greater than 1
while (pq.Count > 1) {
pq.RemoveAt(0);
}
// Return result
return pq[0];
}
static void Main() {
int[] arr = { 1, 7, 9, 2, 12, 3, 3 };
int N = arr.Length;
int K = 3;
Console.Write(findMinimumValue(arr, N, K));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program for the above approach
// Function to split the array into M
// groups such that maximum of the sum
// of all elements of all the groups
// is minimized
function findMinimumValue(arr, N, M)
{
// Sort the array in decreasing order
arr.sort(function(a, b){return a - b});
arr.reverse();
// Initialize priority queue (Min heap)
let pq = [];
// Push 0 for all the M groups
for (let i = 1; i <= M; ++i) {
pq.push(0);
}
pq.sort(function(a, b){return a - b});
// Traverse the array, arr[]
for (let i = 0; i < N; ++i) {
// Pop the group having the
// minimum sum
let val = pq[0];
pq.shift();
// Increment val by arr[i]
val += arr[i];
// Push the new sum of the
// group into the pq
pq.push(val);
pq.sort(function(a, b){return a - b});
}
// Iterate while size of the pq
// is greater than 1
while (pq.length > 1) {
pq.shift();
}
// Return result
return pq[0];
}
let arr = [ 1, 7, 9, 2, 12, 3, 3 ];
let N = arr.length;
let K = 3;
document.write(findMinimumValue(arr, N, K));
// This code is contributed by decode2207.
</script>
Producción:
13
Complejidad de tiempo: O(N*log K)
Espacio auxiliar: O(M)
Publicación traducida automáticamente
Artículo escrito por tmprofessor y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA