Minimice el costo de dividir una array en K subconjuntos de modo que el costo de cada elemento sea su producto con su posición en el subconjunto

Posted on by Rudeus Greyrat

Dada una array arr[] de tamaño N y un entero positivo K , la tarea es encontrar el costo mínimo posible para dividir la array en K subconjuntos , donde el costo del i -ésimo elemento ( indexación basada en 1 ) de cada subconjunto es igual al producto de ese elemento y i .

Ejemplos:

Entrada: arr[] = { 2, 3, 4, 1 }, K = 3 
Salida: 11 
Explicación: 
Divida la array arr[] en K(= 3) subconjuntos { { 4, 1 }, { 2 }, { 3 } } 
Costo total del 1er subconjunto = 4 * 1 + 1 * 2 = 6 
Costo total del 2do subconjunto = 2 * 1 = 2 
Costo total del 3er subconjunto = 3 * 1 = 3 
Por lo tanto, el costo total de K(= 3) subconjuntos es 6 + 2 + 3 = 11.

Entrada: arr[] = { 9, 20, 7, 8 }, K=2 
Salida: 59 
Explicación: 
Dividir la array arr[] en K(= 3) subconjuntos { { 20, 8 }, { 9, 7 } } 
Costo total del primer subconjunto = 20 * 1 + 8 * 2 = 36 
Costo total del segundo subconjunto = 9 * 1 + 7 * 2 = 23 
Por lo tanto, el costo total de K(= 3) subconjuntos es 36 + 23 = 59

Enfoque: El problema se puede resolver usando la técnica Greedy . La idea es dividir los elementos de la array de modo que todos los elementos en los subconjuntos respectivos estén en orden decreciente. Siga los pasos a continuación para resolver el problema:

  • Ordena la array dada en orden descendente .
  • Inicialice una variable, digamos totalCost , para almacenar el costo mínimo para dividir la array en K subconjuntos.
  • Inicialice una variable, digamos X , para almacenar la posición de un elemento en un subconjunto.
  • Iterar sobre el rango [1, N] usando la variable i . Para cada i -ésima operación, incremente el valor de totalCost en ((arr[i]+ …+ arr[i + K]) * X) y actualice i = i + K , X += 1 .
  • Finalmente, imprima el valor de totalCost .

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 to find the minimum cost to
// split array into K subsets
int getMinCost(int* arr, int n, int k)
{
    // Sort the array in descending order
    sort(arr, arr + n, greater<int>());
 
    // Stores minimum cost to split
    // the array into K subsets
    int min_cost = 0;
 
    // Stores position of
    // elements of a subset
    int X = 0;
 
    // Iterate over the range [1, N]
    for (int i = 0; i < n; i += k) {
 
        // Calculate the cost to select
        // X-th element of every subset
        for (int j = i; j < i + k && j < n; j++) {
 
            // Update min_cost
            min_cost += arr[j] * (X + 1);
        }
 
        // Update X
        X++;
    }
 
    return min_cost;
}
 
// Driver Code
int main()
{
    int arr[] = { 9, 20, 7, 8 };
 
    int K = 2;
 
    int N = sizeof(arr)
            / sizeof(arr[0]);
 
    // Function call
    cout << getMinCost(arr, N, K) << endl;
}

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG
{
 
// reverses an array
static void reverse(int a[], int n)
{
    int i, k, t;
    for (i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
}
  
// Function to find the minimum cost to
// split array into K subsets
static int getMinCost(int[] arr, int n, int k)
{
   
    // Sort the array in descending order
    Arrays.sort(arr);
    reverse(arr, n);
  
    // Stores minimum cost to split
    // the array into K subsets
    int min_cost = 0;
  
    // Stores position of
    // elements of a subset
    int X = 0;
  
    // Iterate over the range [1, N]
    for (int i = 0; i < n; i += k)
    {
  
        // Calculate the cost to select
        // X-th element of every subset
        for (int j = i; j < i + k && j < n; j++)
        {
  
            // Update min_cost
            min_cost += arr[j] * (X + 1);
        }
  
        // Update X
        X++;
    }
    return min_cost;
}
   
// Driver code
public static void main(String[] args)
{
    int arr[] = { 9, 20, 7, 8 };
    int K = 2;
    int N = arr.length;
  
    // Function call
    System.out.println( getMinCost(arr, N, K));
}
}
 
// This code is contributed by susmitakundugoaldanga

Python3

# Python program to implement
# the above approach
 
# Function to find the minimum cost to
# split array into K subsets
def getMinCost(arr, n, k):
   
    # Sort the array in descending order
    arr.sort(reverse = True)
 
    # Stores minimum cost to split
    # the array into K subsets
    min_cost = 0;
 
    # Stores position of
    # elements of a subset
    X = 0;
 
    # Iterate over the range [1, N]
    for i in range(0, n, k):
 
        # Calculate the cost to select
        # X-th element of every subset
        for j in range(i, n, 1):
           
            # Update min_cost
            if(j < i + k):
                min_cost += arr[j] * (X + 1);
 
        # Update X
        X += 1;
    return min_cost;
 
# Driver code
if __name__ == '__main__':
    arr = [9, 20, 7, 8];
    K = 2;
    N = len(arr);
 
    # Function call
    print(getMinCost(arr, N, K));
 
# This code is contributed by 29AjayKumar

C#

// C# program to implement
// the above approach
using System;
class GFG
{
 
// reverses an array
static void reverse(int []a, int n)
{
    int i, k, t;
    for (i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
}
  
// Function to find the minimum cost to
// split array into K subsets
static int getMinCost(int[] arr, int n, int k)
{
   
    // Sort the array in descending order
    Array.Sort(arr);
    reverse(arr, n);
  
    // Stores minimum cost to split
    // the array into K subsets
    int min_cost = 0;
  
    // Stores position of
    // elements of a subset
    int X = 0;
  
    // Iterate over the range [1, N]
    for (int i = 0; i < n; i += k)
    {
  
        // Calculate the cost to select
        // X-th element of every subset
        for (int j = i; j < i + k && j < n; j++)
        {
  
            // Update min_cost
            min_cost += arr[j] * (X + 1);
        }
  
        // Update X
        X++;
    }
    return min_cost;
}
   
// Driver code
public static void Main(String[] args)
{
    int []arr = { 9, 20, 7, 8 };
    int K = 2;
    int N = arr.Length;
  
    // Function call
    Console.WriteLine( getMinCost(arr, N, K));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Reverses an array
function reverse(a, n)
{
    var i, k, t;
    for(i = 0; i < n / 2; i++)
    {
        t = a[i];
        a[i] = a[n - i - 1];
        a[n - i - 1] = t;
    }
}
 
// Function to find the minimum cost to
// split array into K subsets
function getMinCost(arr, n, k)
{
     
    // Sort the array in descending order
    arr.sort((a, b) => b - a);
     
    // Stores minimum cost to split
    // the array into K subsets
    var min_cost = 0;
     
    // Stores position of
    // elements of a subset
    var X = 0;
     
    // Iterate over the range [1, N]
    for(var i = 0; i < n; i += k)
    {
         
        // Calculate the cost to select
        // X-th element of every subset
        for(var j = i; j < i + k && j < n; j++)
        {
             
            // Update min_cost
            min_cost += arr[j] * (X + 1);
        }
         
        // Update X
        X++;
    }
    return min_cost;
}
 
// Driver code
var arr = [ 9, 20, 7, 8 ];
var K = 2;
var N = arr.length;
 
// Function call
document.write(getMinCost(arr, N, K));
 
// This code is contributed by rdtank
 
</script>
Producción: 

59

 

Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por bolliranadheer 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 *