Divida la array en K subconjuntos para maximizar su suma de máximos y mínimos

Posted on by Rudeus Greyrat

Dado un entero K y un arreglo A[ ] cuya longitud es múltiplo de K , la tarea es dividir los elementos del arreglo dado en K subconjuntos, cada uno con el mismo número de elementos, de modo que la suma de los elementos máximo y mínimo de cada subconjunto es la suma máxima posible.

Ejemplos: 

Entrada: K = 2, A[ ] = {1, 13, 7, 17, 6, 5} 
Salida: 37 
Explicación: 
1er grupo: {1, 5, 17} máximo = 17, mínimo = 1 
2do grupo: {6 , 7, 13} máximo = 13, mínimo = 6 
Por lo tanto, suma máxima posible = 17 + 1 + 13 + 6 = 37

Entrada: K = 2, A[ ] = {10, 10, 10, 10, 11, 11} 
Salida: 42 
Explicación: 
1er grupo: {11, 10, 10} máximo = 11, mínimo = 10 
2do grupo: {11 , 10, 10} máximo = 11, mínimo = 10 
Por lo tanto, suma máxima posible = 11 + 10 + 11 + 10 = 42

Enfoque ingenuo: 
el enfoque más simple para resolver este problema es generar todos los grupos posibles de K subconjuntos de tamaño N/K y para cada grupo, encontrar el máximo y el mínimo en cada subconjunto y calcular su suma. Una vez calculada la suma de todos los grupos, imprima la suma máxima obtenida. 
Complejidad temporal: O(2 N )  
Espacio auxiliar: O(N)

Enfoque Eficiente: 
La idea es optimizar el enfoque anterior usando la Técnica Greedy . Dado que se necesita la suma máxima del elemento máximo y mínimo de cada subconjunto, intente maximizar el elemento máximo y el elemento mínimo. Para el elemento máximo de cada subconjunto, tome los primeros K elementos más grandes de la array dada e inserte cada uno en diferentes subconjuntos. Para el elemento mínimo de cada subconjunto, de la array ordenada, comenzando desde el índice 0 , seleccione cada elemento siguiente en (N / K) – 1 intervalo ya que el tamaño de cada subconjunto es N / K y cada uno ya contiene un elemento máximo.

Siga los pasos a continuación: 

  • Calcule el número de elementos en cada grupo, es decir (N/K) .
  • Ordene todos los elementos de A[ ] en orden no descendente.
  • Para la suma de los elementos máximos , agregue todos los elementos más grandes de K de la array ordenada.
  • Para la suma de elementos mínimos , a partir del índice 0 , seleccione K elementos cada uno con (N / K) – 1 intervalo y agréguelos.
  • Finalmente, calcule la suma de elementos máximos y la suma de elementos mínimos. Imprime la suma de sus respectivas sumas como respuesta final. 

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints
// the maximum sum possible
void maximumSum(int arr[],
                int n, int k)
{
 
    // Find elements in each group
    int elt = n / k;
 
    int sum = 0;
 
    // Sort all elements in
    // non-descending order
    sort(arr, arr + n);
 
    int count = 0;
    int i = n - 1;
 
    // Add K largest elements
    while (count < k) {
        sum += arr[i];
        i--;
        count++;
    }
 
    count = 0;
    i = 0;
 
    // For sum of minimum
    // elements from each subset
    while (count < k) {
        sum += arr[i];
        i += elt - 1;
        count++;
    }
 
    // Printing the maximum sum
    cout << sum << "\n";
}
 
// Driver Code
int main()
{
    int Arr[] = { 1, 13, 7, 17, 6, 5 };
 
    int K = 2;
 
    int size = sizeof(Arr) / sizeof(Arr[0]);
 
    maximumSum(Arr, size, K);
 
    return 0;
}

Java

// Java program to implement
// the above approach
import java.util.Arrays;
 
class GFG{
     
// Function that prints
// the maximum sum possible
static void maximumSum(int arr[],
                       int n, int k)
{
     
    // Find elements in each group
    int elt = n / k;
 
    int sum = 0;
 
    // Sort all elements in
    // non-descending order
    Arrays.sort(arr);
 
    int count = 0;
    int i = n - 1;
 
    // Add K largest elements
    while (count < k)
    {
        sum += arr[i];
        i--;
        count++;
    }
    count = 0;
    i = 0;
 
    // For sum of minimum
    // elements from each subset
    while (count < k)
    {
        sum += arr[i];
        i += elt - 1;
        count++;
    }
 
    // Printing the maximum sum
    System.out.println(sum);
}
 
// Driver code
public static void main (String[] args)
{
    int Arr[] = { 1, 13, 7, 17, 6, 5 };
 
    int K = 2;
 
    int size = Arr.length;
 
    maximumSum(Arr, size, K);
}
}
 
// This code is contributed by Shubham Prakash

Python3

# Python3 program to implement
# the above approach
 
# Function that prints
# the maximum sum possible
def maximumSum(arr, n, k):
   
    # Find elements in each group
    elt = n // k;
 
    sum = 0;
 
    # Sort all elements in
    # non-descending order
    arr.sort();
 
    count = 0;
    i = n - 1;
 
    # Add K largest elements
    while (count < k):
        sum += arr[i];
        i -= 1;
        count += 1;
 
    count = 0;
    i = 0;
 
    # For sum of minimum
    # elements from each subset
    while (count < k):
        sum += arr[i];
        i += elt - 1;
        count += 1;
 
    # Printing the maximum sum
    print(sum);
 
# Driver code
if __name__ == '__main__':
    Arr = [1, 13, 7, 17, 6, 5];
 
    K = 2;
 
    size = len(Arr);
 
    maximumSum(Arr, size, K);
 
# This code is contributed by sapnasingh4991

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
     
// Function that prints
// the maximum sum possible
static void maximumSum(int []arr,
                       int n, int k)
{
     
    // Find elements in each group
    int elt = n / k;
 
    int sum = 0;
 
    // Sort all elements in
    // non-descending order
    Array.Sort(arr);
 
    int count = 0;
    int i = n - 1;
 
    // Add K largest elements
    while (count < k)
    {
        sum += arr[i];
        i--;
        count++;
    }
    count = 0;
    i = 0;
 
    // For sum of minimum
    // elements from each subset
    while (count < k)
    {
        sum += arr[i];
        i += elt - 1;
        count++;
    }
 
    // Printing the maximum sum
    Console.WriteLine(sum);
}
 
// Driver code
public static void Main(String[] args)
{
    int []Arr = { 1, 13, 7, 17, 6, 5 };
 
    int K = 2;
 
    int size = Arr.Length;
 
    maximumSum(Arr, size, K);
}
}
 
// This code is contributed by amal kumar choubey

Javascript

<script>
 
// Javascript program implementation
// of the approach
 
// Function that prints
// the maximum sum possible
function maximumSum(arr, n, k)
{
      
    // Find elements in each group
    let elt = (n / k);
  
    let sum = 0;
  
    // Sort all elements in
    // non-descending order
    arr.sort((a, b) => a - b);
  
    let count = 0;
    let i = n - 1;
  
    // Add K largest elements
    while (count < k)
    {
        sum += arr[i];
        i--;
        count++;
    }
    count = 0;
    i = 0;
  
    // For sum of minimum
    // elements from each subset
    while (count < k)
    {
        sum += arr[i];
        i += elt - 1;
        count++;
    }
  
    // Printing the maximum sum
    document.write(sum);
}
 
// Driver Code
     
       let Arr = [ 1, 13, 7, 17, 6, 5 ];
  
    let K = 2;
  
    let size = Arr.length;
  
    maximumSum(Arr, size, K);
          
</script>
Producción: 

37

 

Complejidad temporal: O(N*logN)  
Espacio auxiliar: O(1)
 

Publicación traducida automáticamente

Artículo escrito por nitinkr8991 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *