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: 1
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>
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