Diferencia absoluta mínima de cargas de servidor

Hay algunos procesos que necesitan ser ejecutados. La cantidad de carga que ese proceso provoca en un servidor que lo ejecuta se representa mediante un único número entero. La carga total provocada en un servidor es la suma de las cargas de todos los procesos que se ejecutan en ese servidor. Tiene a su disposición dos servidores, en los que se pueden ejecutar los procesos mencionados. Su objetivo es distribuir los procesos dados entre esos dos servidores de manera que se minimice la diferencia absoluta de sus cargas. 
Dada una array de A[] de N enteros, que representa las cargas causadas por procesos sucesivos, la tarea es imprimir la diferencia mínima absoluta de las cargas del servidor. 
Ejemplos:

Entrada: A[] = {1, 2, 3, 4, 5} 
Salida:
Explicación: 
Distribuya los procesos con cargas {1, 2, 4} en el primer servidor y {3, 5} en el segundo servidor, así que sus cargas totales serán 7 y 8, respectivamente. 
La diferencia de sus cargas será igual a 1.

Entrada: A[] = {10, 10, 9, 9, 2} 
Salida: 0

Enfoque ingenuo: el enfoque más simple para resolver el problema es generar todas las posibilidades de distribución de carga y encontrar la mínima diferencia posible entre todas las posibles combinaciones de cargas de los dos servidores.

Complejidad temporal: O(2 N
Espacio auxiliar: O(1)

Enfoque eficiente: el problema se puede visualizar como una variación del problema de la mochila 0/1 en el que se dan 2 servidores y tenemos que distribuir las cargas de la manera más equitativa posible. Por lo tanto, se puede resolver usando Programación Dinámica . A continuación se muestran los pasos:

  • Calcule la carga requerida , que es igual a (suma de todas las cargas / 2) , ya que las cargas deben distribuirse de la manera más equitativa posible.
  • Cree una tabla de memorización DP[][] para considerar todas las posibles cargas del servidor en el rango [1, required_load] .
  • El estado DP[i][j] almacena el valor máximo de j – carga considerando hasta el i -ésimo elemento. Entonces, considerando l i (carga en i -ésima fila ), se pueden completar todas las columnas que tengan valores de carga > l i .
  • Ahora surgen dos posibilidades, ya sea para llenar l i en la columna dada o no.
  • Ahora, tome un máximo de las dos posibilidades anteriores, es decir

DP[i][j] = max(DP[i – 1][j], DP[i – 1][j – l i ] + l i ]

  • Finalmente, DP[n][required_load] contendrá la carga en server1 que está lo más equilibrada posible.

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

C++14

// C++14 program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function which returns the minimum
// difference of loads
int minServerLoads(int n, vector<int>& servers)
{
     
    // Compute the overall server load
    int totalLoad = 0;
    for(int i : servers) totalLoad += i;
 
    int requiredLoad = totalLoad / 2;
 
    // Stores the results of subproblems
    vector<vector<int>> dp(n + 1,
    vector<int>(requiredLoad + 1, 0));
 
    // Fill the partition table
    // in bottom up manner
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 1; j < requiredLoad + 1; j++)
        {
             
            // If i-th server is included
            if (servers[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
 
            // If i-th server is excluded
            else
                dp[i][j] = max(dp[i - 1][j],
                          servers[i - 1] +
                        dp[i - 1][j - servers[i - 1]]);
        }
    }
 
    // Server A load: total_sum-ans
    // Server B load: ans
    // Diff: abs(total_sum-2 * ans)
    return totalLoad - 2 * dp[n][requiredLoad];
}
 
// Driver Code
int main()
{
    int N = 5;
     
    vector<int> servers = { 1, 2, 3, 4, 5 };
     
    // Function call
    cout << (minServerLoads(N, servers));
}
 
// This code is contributed by mohit kumar 29

Java

// Java program to implement
// the above approach
import java.util.*;
class GFG {
 
    // Function which returns the minimum
    // difference of loads
    static int minServerLoads(int n, int[] servers)
    {
        // Compute the overall server load
        int totalLoad = 0;
        for (int i = 0; i < servers.length; i++)
            totalLoad += servers[i];
        int requiredLoad = totalLoad / 2;
 
        // Stores the results of subproblems
        int dp[][] = new int[n + 1][requiredLoad + 1];
 
        // Fill the partition table
        // in bottom up manner
        for (int i = 1; i < n + 1; i++)
        {
            for (int j = 1; j < requiredLoad + 1; j++)
            {
                // If i-th server is included
                if (servers[i - 1] > j)
                    dp[i][j] = dp[i - 1][j];
 
                // If i-th server is excluded
                else
                    dp[i][j] = Math.max(dp[i - 1][j],
                                        servers[i - 1] +
                                        dp[i - 1][j - servers[i - 1]]);
            }
        }
 
        // Server A load: total_sum-ans
        // Server B load: ans
        // Diff: abs(total_sum-2 * ans)
        return totalLoad - 2 * dp[n][requiredLoad];
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 5;
        int servers[] = {1, 2, 3, 4, 5};
 
        // Function call
        System.out.print(minServerLoads(N, servers));
    }
}
 
// This code is contributed by Chitranayal

Python3

# Python3 program for the above approach
 
# Function which returns the minimum
# difference of loads
def minServerLoads(n, servers):
 
    # Compute the overall server load
    totalLoad = sum(servers)
 
    requiredLoad = totalLoad // 2
 
    # Stores the results of subproblems
    dp = [[0 for col in range(requiredLoad + 1)]
          for row in range(n + 1)]
 
    # Fill the partition table
    # in bottom up manner
    for i in range(1, n + 1):
        for j in range(1, requiredLoad + 1):
 
            # If i-th server is included
            if servers[i-1] > j:
                dp[i][j] = dp[i-1][j]
 
            # If i-th server is excluded
            else:
                dp[i][j] = max(dp[i-1][j],
                           servers[i-1] +
                           dp[i-1][j-servers[i-1]])
 
    # Server A load: total_sum-ans
    # Server B load: ans
    # Diff: abs(total_sum-2 * ans)
    return totalLoad - 2 * dp[n][requiredLoad]
 
# Driver Code
 
N = 5;
 
servers = [1, 2, 3, 4, 5]
 
# Function Call
print(minServerLoads(N, servers))

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
// Function which returns the minimum
// difference of loads
static int minServerLoads(int n, int[] servers)
{
     
    // Compute the overall server load
    int totalLoad = 0;
    for(int i = 0; i < servers.Length; i++)
        totalLoad += servers[i];
         
    int requiredLoad = totalLoad / 2;
 
    // Stores the results of subproblems
    int [,]dp = new int[n + 1, requiredLoad + 1];
 
    // Fill the partition table
    // in bottom up manner
    for(int i = 1; i < n + 1; i++)
    {
        for(int j = 1; j < requiredLoad + 1; j++)
        {
             
            // If i-th server is included
            if (servers[i - 1] > j)
                dp[i, j] = dp[i - 1, j];
 
            // If i-th server is excluded
            else
                dp[i, j] = Math.Max(dp[i - 1, j],
                               servers[i - 1] +
                                    dp[i - 1, j -
                               servers[i - 1]]);
        }
    }
 
    // Server A load: total_sum-ans
    // Server B load: ans
    // Diff: abs(total_sum-2 * ans)
    return totalLoad - 2 * dp[n, requiredLoad];
}
 
// Driver Code
public static void Main(string[] args)
{
    int N = 5;
    int []servers = { 1, 2, 3, 4, 5 };
 
    // Function call
    Console.Write(minServerLoads(N, servers));
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// JavaScript program to implement
// the above approach
 
// Function which returns the minimum
// difference of loads
function minServerLoads(n, servers)
{
     
    // Compute the overall server load
    var totalLoad = 0;
 
    servers.forEach(i => {
        totalLoad+=i;
    });
 
    var requiredLoad = parseInt(totalLoad / 2);
 
    // Stores the results of subproblems
    var dp =
    Array.from(Array(n+1), ()=> Array(requiredLoad+1).fill(0));
 
    // Fill the partition table
    // in bottom up manner
    for(var i = 1; i < n + 1; i++)
    {
        for(var j = 1; j < requiredLoad + 1; j++)
        {
             
            // If i-th server is included
            if (servers[i - 1] > j)
                dp[i][j] = dp[i - 1][j];
 
            // If i-th server is excluded
            else
                dp[i][j] = Math.max(dp[i - 1][j],
                          servers[i - 1] +
                        dp[i - 1][j - servers[i - 1]]);
        }
    }
 
    // Server A load: total_sum-ans
    // Server B load: ans
    // Diff: abs(total_sum-2 * ans)
    return totalLoad - 2 * dp[n][requiredLoad];
}
 
// Driver Code
var N = 5;
var servers = [1, 2, 3, 4, 5];
 
// Function call
document.write(minServerLoads(N, servers));
 
 
</script>
Producción: 

1

Complejidad de tiempo: O(N*S) donde N es el número de servidores y S es la suma de la carga de todos los servidores. 
Espacio Auxiliar: O(N*S)

Publicación traducida automáticamente

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