Divida una array en K subarreglo con la condición dada

Dada una array arr[] y un entero K . La tarea es dividir el arreglo en K partes (subarreglo) de tal manera que la suma de los valores de todos los subarreglos sea mínima.
El valor de cada subarreglo se define como: 
 

  • Tome el máximo de ese subarreglo.
  • Resta cada elemento del subarreglo con el máximo.
  • Tome la suma de todos los valores después de la resta.

La tarea es minimizar la suma de los valores después de dividir la array en K partes.
Ejemplos: 
 

Entrada: arr[] = { 2, 9, 5, 4, 8, 3, 6 }, K = 2 
Salida: 19 
Explicación: 
Los dos grupos son: {2} con max = 2 y {9, 5, 4, 8, 3, 6} con max=9, 
suma de la diferencia del primer grupo = 2 – 2 = 0, 
suma de la diferencia del segundo grupo = (9-9) + (9-5) + (9-4) + ( 9-8) + (9-3) + (9-6) = 19
Entrada: arr[] = { 12, 20, 30, 14, 25}, K = 3 
Salida: 19 
 

Enfoque: 
La solución de fuerza bruta será probar todas las particiones posibles y tomar el mínimo total. Aunque esta solución es exponencial en el tiempo. En la solución recursiva, hay muchos subproblemas superpuestos que pueden optimizarse mediante programación dinámica.
Entonces, podemos formar una fórmula recursiva básica y que calcule todas las soluciones posibles y encuentre la mejor solución posible. Podemos ver que la solución recursiva tiene muchos subproblemas superpuestos, podemos reducir la complejidad usando la programación dinámica.
Fórmula recursiva: 
F(i, K) = { min de todos los valores tales que j < i [ max(Arr[i..j]) * (i – j + 1) – Sum(A[i…j] ] } + F(j, K-1) 
El enfoque ascendente se puede utilizar para calcular primero los valores de los subproblemas y almacenarlos.Aquí
dp [i][j]define el valor mínimo que se puede obtener si la array parte del índice i y tiene una partición j .
Entonces, la respuesta a los problemas será dp[0][K] , una array que comienza en 0 y tiene K particiones.
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to divide an array into k
// parts such that the sum of difference
// of every element with the maximum element
// of that part is minimum
int divideArray(int arr[], int n, int k)
{
    // Dp to store the values
    int dp[500][500] = { 0 };
 
    k -= 1;
 
    // Fill up the dp table
    for (int i = n - 1; i >= 0; i--) {
        for (int j = 0; j <= k; j++) {
            // Intitilize maximum value
            dp[i][j] = INT_MAX;
 
            // Max element and the sum
            int max_ = -1, sum = 0;
 
            // Run a loop from i to n
            for (int l = i; l < n; l++) {
                // Find the maximum number
                // from i to l and the sum
                // from i to l
                max_ = max(max_, arr[l]);
                sum += arr[l];
 
                // Find the sum of difference
                // of every element with the
                // maximum element
                int diff = (l - i + 1) * max_ - sum;
 
                // If the array can be divided
                if (j > 0)
                    dp[i][j]
                        = min(dp[i][j],
                              diff + dp[l + 1][j - 1]);
                else
                    dp[i][j] = diff;
            }
        }
    }
 
    // Returns the minimum sum
    // in K parts
    return dp[0][k];
}
 
// Driver code
int main()
{
    int arr[] = { 2, 9, 5, 4, 8, 3, 6 };
    int n = sizeof(arr) / sizeof(int);
    int k = 2;
 
    cout << divideArray(arr, n, k) << "\n";
 
    return 0;
}

Java

// Java implementation of the above approach
class GFG
{
     
    // Function to divide an array into k
    // parts such that the sum of difference
    // of every element with the maximum element
    // of that part is minimum
    static int divideArray(int arr[], int n, int k)
    {
        // Dp to store the values
        int dp[][] = new int[500][500];
         
        int i, j;
         
        for(i = 0; i < 500; i++)
            for(j = 0; j < 500; j++)
                dp[i][j] = 0;
                 
        k -= 1;
     
        // Fill up the dp table
        for (i = n - 1; i >= 0; i--)
        {
            for (j = 0; j <= k; j++)
            {
                 
                // Intitilize maximum value
                dp[i][j] = Integer.MAX_VALUE;
     
                // Max element and the sum
                int max_ = -1, sum = 0;
     
                // Run a loop from i to n
                for (int l = i; l < n; l++)
                {
                    // Find the maximum number
                    // from i to l and the sum
                    // from i to l
                    max_ = Math.max(max_, arr[l]);
                    sum += arr[l];
     
                    // Find the sum of difference
                    // of every element with the
                    // maximum element
                    int diff = (l - i + 1) * max_ - sum;
     
                    // If the array can be divided
                    if (j > 0)
                        dp[i][j] = Math.min(dp[i][j], diff +
                                            dp[l + 1][j - 1]);
                    else
                        dp[i][j] = diff;
                }
            }
        }
     
        // Returns the minimum sum
        // in K parts
        return dp[0][k];
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr[] = { 2, 9, 5, 4, 8, 3, 6 };
        int n = arr.length;
        int k = 2;
     
        System.out.println(divideArray(arr, n, k));
    }
}
 
// This code is contributed by AnkitRai01

Python3

# Python3 implementation of the above approach
 
# Function to divide an array into k
# parts such that the summ of difference
# of every element with the maximum element
# of that part is minimum
def divideArray(arr, n, k):
     
    # Dp to store the values
    dp = [[0 for i in range(500)]
             for i in range(500)]
 
    k -= 1
 
    # Fill up the dp table
    for i in range(n - 1, -1, -1):
        for j in range(0, k + 1):
             
            # Intitilize maximum value
            dp[i][j] = 10**9
 
            # Max element and the summ
            max_ = -1
            summ = 0
 
            # Run a loop from i to n
            for l in range(i, n):
                 
                # Find the maximum number
                # from i to l and the summ
                # from i to l
                max_ = max(max_, arr[l])
                summ += arr[l]
 
                # Find the summ of difference
                # of every element with the
                # maximum element
                diff = (l - i + 1) * max_ - summ
 
                # If the array can be divided
                if (j > 0):
                    dp[i][j]= min(dp[i][j], diff +
                                  dp[l + 1][j - 1])
                else:
                    dp[i][j] = diff
 
    # Returns the minimum summ
    # in K parts
    return dp[0][k]
 
# Driver code
arr = [2, 9, 5, 4, 8, 3, 6]
n = len(arr)
k = 2
 
print(divideArray(arr, n, k))
 
# This code is contributed by Mohit Kumar

C#

// C# implementation of above approach
using System;
 
class GFG
{
     
    // Function to divide an array into k
    // parts such that the sum of difference
    // of every element with the maximum element
    // of that part is minimum
    static int divideArray(int []arr, int n, int k)
    {
        // Dp to store the values
        int [,]dp = new int[500, 500];
         
        int i, j;
         
        for(i = 0; i < 500; i++)
            for(j = 0; j < 500; j++)
                dp[i, j] = 0;
                 
        k -= 1;
     
        // Fill up the dp table
        for (i = n - 1; i >= 0; i--)
        {
            for (j = 0; j <= k; j++)
            {
                 
                // Intitilize maximum value
                dp[i, j] = int.MaxValue;
     
                // Max element and the sum
                int max_ = -1, sum = 0;
     
                // Run a loop from i to n
                for (int l = i; l < n; l++)
                {
                    // Find the maximum number
                    // from i to l and the sum
                    // from i to l
                    max_ = Math.Max(max_, arr[l]);
                    sum += arr[l];
     
                    // Find the sum of difference
                    // of every element with the
                    // maximum element
                    int diff = (l - i + 1) * max_ - sum;
     
                    // If the array can be divided
                    if (j > 0)
                        dp[i, j] = Math.Min(dp[i, j], diff +
                                            dp[l + 1, j - 1]);
                    else
                        dp[i, j] = diff;
                }
            }
        }
     
        // Returns the minimum sum
        // in K parts
        return dp[0, k];
    }
     
    // Driver code
    public static void Main (String[] args)
    {
        int []arr = { 2, 9, 5, 4, 8, 3, 6 };
        int n = arr.Length;
        int k = 2;
     
        Console.WriteLine(divideArray(arr, n, k));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Function to divide an array into k
// parts such that the sum of difference
// of every element with the maximum element
// of that part is minimum
function divideArray(arr, n, k)
{
    // Dp to store the values
    var dp = Array.from(Array(500), ()=> Array(500).fill(0));
 
    k -= 1;
 
    // Fill up the dp table
    for (var i = n - 1; i >= 0; i--) {
        for (var j = 0; j <= k; j++) {
            // Intitilize maximum value
            dp[i][j] = 1000000000;
 
            // Max element and the sum
            var max_ = -1, sum = 0;
 
            // Run a loop from i to n
            for (var l = i; l < n; l++) {
                // Find the maximum number
                // from i to l and the sum
                // from i to l
                max_ = Math.max(max_, arr[l]);
                sum += arr[l];
 
                // Find the sum of difference
                // of every element with the
                // maximum element
                var diff = (l - i + 1) * max_ - sum;
 
                // If the array can be divided
                if (j > 0)
                    dp[i][j]
                        = Math.min(dp[i][j],
                              diff + dp[l + 1][j - 1]);
                else
                    dp[i][j] = diff;
            }
        }
    }
 
    // Returns the minimum sum
    // in K parts
    return dp[0][k];
}
 
// Driver code
var arr = [2, 9, 5, 4, 8, 3, 6 ];
var n = arr.length;
var k = 2;
document.write( divideArray(arr, n, k) + "<br>");
 
</script>
Producción: 

19

 

Complejidad de tiempo: O(n*n*k), n es el tamaño de la array

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

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