Dado un número de amigos que tienen que dar o recibir una cierta cantidad de dinero unos de otros. Diseñe un algoritmo mediante el cual se minimice el flujo de caja total entre todos los amigos.
Ejemplo:
El siguiente diagrama muestra las deudas de entrada a liquidar.
Las deudas anteriores se pueden liquidar de la siguiente manera optimizada
La idea es utilizar el algoritmo Greedy en el que, en cada paso, liquidar todas las cantidades de una persona y repetir para las n-1 personas restantes.
¿Cómo elegir a la primera persona? Para elegir la primera persona, calcule el monto neto para cada persona donde el monto neto se obtiene restando todas las deudas (montos a pagar) de todos los créditos (montos a pagar). Una vez que se evalúe la cantidad neta para cada persona, encuentre dos personas con cantidades netas máximas y mínimas. Estas dos personas son las más acreedoras y deudoras. La persona con un mínimo de dos es nuestra primera persona en ser liquidada y eliminada de la lista. Sea x el mínimo de dos cantidades. Pagamos la cantidad ‘x’ del deudor máximo al acreedor máximo y liquidamos a una persona. Si x es igual al débito máximo, entonces se liquida el deudor máximo, de lo contrario se liquida el acreedor máximo.
El siguiente es un algoritmo detallado.
Haga lo siguiente para cada persona Pi donde i es de 0 a n-1.
- Calcule la cantidad neta para cada persona. El monto neto de la persona ‘i’ se puede calcular restando la suma de todas las deudas de la suma de todos los créditos.
- Encuentre las dos personas que son máximo acreedor y máximo deudor. Deje que el monto máximo a acreditar al acreedor máximo sea maxCredit y el monto máximo a debitar del deudor máximo sea maxDebit. Sea Pd el deudor máximo y Pc el acreedor máximo.
- Encuentre el mínimo de maxDebit y maxCredit. Sea mínimo dos x. Débito ‘x’ de Pd y crédito de este monto a Pc
- Si x es igual a maxCredit, elimine Pc del conjunto de personas y recurra para las (n-1) personas restantes.
- Si x es igual a maxDebit, elimine Pd del conjunto de personas y recurra a las (n-1) personas restantes.
Gracias a Balaji S por sugerir este método en un comentario aquí .
La siguiente es la implementación del algoritmo anterior.
C++
// C++ program to find maximum cash flow among a set of persons
#include<iostream>
using namespace std;
// Number of persons (or vertices in the graph)
#define N 3
// A utility function that returns index of minimum value in arr[]
int getMin(int arr[])
{
int minInd = 0;
for (int i=1; i<N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
// A utility function that returns index of maximum value in arr[]
int getMax(int arr[])
{
int maxInd = 0;
for (int i=1; i<N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
// A utility function to return minimum of 2 values
int minOf2(int x, int y)
{
return (x<y)? x: y;
}
// amount[p] indicates the net amount to be credited/debited
// to/from person 'p'
// If amount[p] is positive, then i'th person will amount[i]
// If amount[p] is negative, then i'th person will give -amount[i]
void minCashFlowRec(int amount[])
{
// Find the indexes of minimum and maximum values in amount[]
// amount[mxCredit] indicates the maximum amount to be given
// (or credited) to any person .
// And amount[mxDebit] indicates the maximum amount to be taken
// (or debited) from any person.
// So if there is a positive value in amount[], then there must
// be a negative value
int mxCredit = getMax(amount), mxDebit = getMin(amount);
// If both amounts are 0, then all amounts are settled
if (amount[mxCredit] == 0 && amount[mxDebit] == 0)
return;
// Find the minimum of two amounts
int min = minOf2(-amount[mxDebit], amount[mxCredit]);
amount[mxCredit] -= min;
amount[mxDebit] += min;
// If minimum is the maximum amount to be
cout << "Person " << mxDebit << " pays " << min
<< " to " << "Person " << mxCredit << endl;
// Recur for the amount array. Note that it is guaranteed that
// the recursion would terminate as either amount[mxCredit]
// or amount[mxDebit] becomes 0
minCashFlowRec(amount);
}
// Given a set of persons as graph[] where graph[i][j] indicates
// the amount that person i needs to pay person j, this function
// finds and prints the minimum cash flow to settle all debts.
void minCashFlow(int graph[][N])
{
// Create an array amount[], initialize all value in it as 0.
int amount[N] = {0};
// Calculate the net amount to be paid to person 'p', and
// stores it in amount[p]. The value of amount[p] can be
// calculated by subtracting debts of 'p' from credits of 'p'
for (int p=0; p<N; p++)
for (int i=0; i<N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
minCashFlowRec(amount);
}
// Driver program to test above function
int main()
{
// graph[i][j] indicates the amount that person i needs to
// pay person j
int graph[N][N] = { {0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0},};
// Print the solution
minCashFlow(graph);
return 0;
}
Java
// Java program to find maximum cash
// flow among a set of persons
class GFG
{
// Number of persons (or vertices in the graph)
static final int N = 3;
// A utility function that returns
// index of minimum value in arr[]
static int getMin(int arr[])
{
int minInd = 0;
for (int i = 1; i < N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
// A utility function that returns
// index of maximum value in arr[]
static int getMax(int arr[])
{
int maxInd = 0;
for (int i = 1; i < N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
// A utility function to return minimum of 2 values
static int minOf2(int x, int y)
{
return (x < y) ? x: y;
}
// amount[p] indicates the net amount
// to be credited/debited to/from person 'p'
// If amount[p] is positive, then
// i'th person will amount[i]
// If amount[p] is negative, then
// i'th person will give -amount[i]
static void minCashFlowRec(int amount[])
{
// Find the indexes of minimum and
// maximum values in amount[]
// amount[mxCredit] indicates the maximum amount
// to be given (or credited) to any person .
// And amount[mxDebit] indicates the maximum amount
// to be taken(or debited) from any person.
// So if there is a positive value in amount[],
// then there must be a negative value
int mxCredit = getMax(amount), mxDebit = getMin(amount);
// If both amounts are 0, then
// all amounts are settled
if (amount[mxCredit] == 0 && amount[mxDebit] == 0)
return;
// Find the minimum of two amounts
int min = minOf2(-amount[mxDebit], amount[mxCredit]);
amount[mxCredit] -= min;
amount[mxDebit] += min;
// If minimum is the maximum amount to be
System.out.println("Person " + mxDebit + " pays " + min
+ " to " + "Person " + mxCredit);
// Recur for the amount array.
// Note that it is guaranteed that
// the recursion would terminate
// as either amount[mxCredit] or
// amount[mxDebit] becomes 0
minCashFlowRec(amount);
}
// Given a set of persons as graph[]
// where graph[i][j] indicates
// the amount that person i needs to
// pay person j, this function
// finds and prints the minimum
// cash flow to settle all debts.
static void minCashFlow(int graph[][])
{
// Create an array amount[],
// initialize all value in it as 0.
int amount[]=new int[N];
// Calculate the net amount to
// be paid to person 'p', and
// stores it in amount[p]. The
// value of amount[p] can be
// calculated by subtracting
// debts of 'p' from credits of 'p'
for (int p = 0; p < N; p++)
for (int i = 0; i < N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
minCashFlowRec(amount);
}
// Driver code
public static void main (String[] args)
{
// graph[i][j] indicates the amount
// that person i needs to pay person j
int graph[][] = { {0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0},};
// Print the solution
minCashFlow(graph);
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 program to find maximum
# cash flow among a set of persons
# Number of persons(or vertices in graph)
N = 3
# A utility function that returns
# index of minimum value in arr[]
def getMin(arr):
minInd = 0
for i in range(1, N):
if (arr[i] < arr[minInd]):
minInd = i
return minInd
# A utility function that returns
# index of maximum value in arr[]
def getMax(arr):
maxInd = 0
for i in range(1, N):
if (arr[i] > arr[maxInd]):
maxInd = i
return maxInd
# A utility function to
# return minimum of 2 values
def minOf2(x, y):
return x if x < y else y
# amount[p] indicates the net amount to
# be credited/debited to/from person 'p'
# If amount[p] is positive, then i'th
# person will amount[i]
# If amount[p] is negative, then i'th
# person will give -amount[i]
def minCashFlowRec(amount):
# Find the indexes of minimum
# and maximum values in amount[]
# amount[mxCredit] indicates the maximum
# amount to be given(or credited) to any person.
# And amount[mxDebit] indicates the maximum amount
# to be taken (or debited) from any person.
# So if there is a positive value in amount[],
# then there must be a negative value
mxCredit = getMax(amount)
mxDebit = getMin(amount)
# If both amounts are 0,
# then all amounts are settled
if (amount[mxCredit] == 0 and amount[mxDebit] == 0):
return 0
# Find the minimum of two amounts
min = minOf2(-amount[mxDebit], amount[mxCredit])
amount[mxCredit] -=min
amount[mxDebit] += min
# If minimum is the maximum amount to be
print("Person " , mxDebit , " pays " , min
, " to " , "Person " , mxCredit)
# Recur for the amount array. Note that
# it is guaranteed that the recursion
# would terminate as either amount[mxCredit]
# or amount[mxDebit] becomes 0
minCashFlowRec(amount)
# Given a set of persons as graph[] where
# graph[i][j] indicates the amount that
# person i needs to pay person j, this
# function finds and prints the minimum
# cash flow to settle all debts.
def minCashFlow(graph):
# Create an array amount[],
# initialize all value in it as 0.
amount = [0 for i in range(N)]
# Calculate the net amount to be paid
# to person 'p', and stores it in amount[p].
# The value of amount[p] can be calculated by
# subtracting debts of 'p' from credits of 'p'
for p in range(N):
for i in range(N):
amount[p] += (graph[i][p] - graph[p][i])
minCashFlowRec(amount)
# Driver code
# graph[i][j] indicates the amount
# that person i needs to pay person j
graph = [ [0, 1000, 2000],
[0, 0, 5000],
[0, 0, 0] ]
minCashFlow(graph)
# This code is contributed by Anant Agarwal.
C#
// C# program to find maximum cash
// flow among a set of persons
using System;
class GFG
{
// Number of persons (or
// vertices in the graph)
static int N = 3;
// A utility function that returns
// index of minimum value in arr[]
static int getMin(int []arr)
{
int minInd = 0;
for (int i = 1; i < N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
// A utility function that returns
// index of maximum value in arr[]
static int getMax(int []arr)
{
int maxInd = 0;
for (int i = 1; i < N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
// A utility function to return
// minimum of 2 values
static int minOf2(int x, int y)
{
return (x < y) ? x: y;
}
// amount[p] indicates the net amount
// to be credited/debited to/from person 'p'
// If amount[p] is positive, then
// i'th person will amount[i]
// If amount[p] is negative, then
// i'th person will give -amount[i]
static void minCashFlowRec(int []amount)
{
// Find the indexes of minimum and
// maximum values in amount[]
// amount[mxCredit] indicates the maximum amount
// to be given (or credited) to any person .
// And amount[mxDebit] indicates the maximum amount
// to be taken(or debited) from any person.
// So if there is a positive value in amount[],
// then there must be a negative value
int mxCredit = getMax(amount), mxDebit = getMin(amount);
// If both amounts are 0, then
// all amounts are settled
if (amount[mxCredit] == 0 &&
amount[mxDebit] == 0)
return;
// Find the minimum of two amounts
int min = minOf2(-amount[mxDebit], amount[mxCredit]);
amount[mxCredit] -= min;
amount[mxDebit] += min;
// If minimum is the maximum amount to be
Console.WriteLine("Person " + mxDebit +
" pays " + min + " to " +
"Person " + mxCredit);
// Recur for the amount array.
// Note that it is guaranteed that
// the recursion would terminate
// as either amount[mxCredit] or
// amount[mxDebit] becomes 0
minCashFlowRec(amount);
}
// Given a set of persons as graph[]
// where graph[i][j] indicates
// the amount that person i needs to
// pay person j, this function
// finds and prints the minimum
// cash flow to settle all debts.
static void minCashFlow(int [,]graph)
{
// Create an array amount[],
// initialize all value in it as 0.
int []amount=new int[N];
// Calculate the net amount to
// be paid to person 'p', and
// stores it in amount[p]. The
// value of amount[p] can be
// calculated by subtracting
// debts of 'p' from credits of 'p'
for (int p = 0; p < N; p++)
for (int i = 0; i < N; i++)
amount[p] += (graph[i,p] - graph[p,i]);
minCashFlowRec(amount);
}
// Driver code
public static void Main ()
{
// graph[i][j] indicates the amount
// that person i needs to pay person j
int [,]graph = { {0, 1000, 2000},
{0, 0, 5000},
{0, 0, 0},};
// Print the solution
minCashFlow(graph);
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP program to find maximum cash
// flow among a set of persons
// Number of persons (or vertices in the graph)
$N = 3;
// A utility function that returns
// index of minimum value in arr[]
function getMin($arr)
{
global $N;
$minInd = 0;
for ($i = 1; $i < $N; $i++)
if ($arr[$i] < $arr[$minInd])
$minInd = $i;
return $minInd;
}
// A utility function that returns
// index of maximum value in arr[]
function getMax($arr)
{
global $N;
$maxInd = 0;
for ($i = 1; $i < $N; $i++)
if ($arr[$i] > $arr[$maxInd])
$maxInd = $i;
return $maxInd;
}
// A utility function to return minimum of 2 values
function minOf2($x, $y)
{
return ($x < $y)? $x: $y;
}
// amount[p] indicates the net amount
// to be credited/debited to/from person 'p'
// If amount[p] is positive, then i'th
// person will amount[i]
// If amount[p] is negative, then i'th
// person will give -amount[i]
function minCashFlowRec($amount)
{
// Find the indexes of minimum and
// maximum values in amount[]
// amount[mxCredit] indicates the
// maximum amount to be given
// (or credited) to any person .
// And amount[mxDebit] indicates the
// maximum amount to be taken
// (or debited) from any person.
// So if there is a positive value in
// amount[], then there must
// be a negative value
$mxCredit = getMax($amount);
$mxDebit = getMin($amount);
// If both amounts are 0, then
// all amounts are settled
if ($amount[$mxCredit] == 0 &&
$amount[$mxDebit] == 0)
return;
// Find the minimum of two amounts
$min = minOf2(-$amount[$mxDebit], $amount[$mxCredit]);
$amount[$mxCredit] -= $min;
$amount[$mxDebit] += $min;
// If minimum is the maximum amount to be
echo "Person ".$mxDebit." pays ".$min." to Person ".$mxCredit."\n";
// Recur for the amount array. Note
// that it is guaranteed that the
// recursion would terminate as
// either amount[mxCredit]
// or amount[mxDebit] becomes 0
minCashFlowRec($amount);
}
// Given a set of persons as graph[]
// where graph[i][j] indicates the
// amount that person i needs to
// pay person j, this function finds
// and prints the minimum cash flow
// to settle all debts.
function minCashFlow($graph)
{
global $N;
// Create an array amount[],
// initialize all value in it as 0.
$amount=array_fill(0, $N, 0);
// Calculate the net amount to be
// paid to person 'p', and stores
// it in amount[p]. The value of
// amount[p] can be calculated by
// subtracting debts of 'p' from
// credits of 'p'
for ($p = 0; $p < $N; $p++)
for ($i = 0; $i < $N; $i++)
$amount[$p] += ($graph[$i][$p] - $graph[$p][$i]);
minCashFlowRec($amount);
}
// Driver code
// graph[i][j] indicates the amount
// that person i needs to pay person j
$graph = array(array(0, 1000, 2000),
array(0, 0, 5000),
array(0, 0, 0));
// Print the solution
minCashFlow($graph);
// This code is contributed by mits
?>
Javascript
<script>
// javascript program to find maximum cash
// flow among a set of persons
// Number of persons (or vertices in the graph)
var N = 3;
// A utility function that returns
// index of minimum value in arr
function getMin(arr)
{
var minInd = 0;
for (i = 1; i < N; i++)
if (arr[i] < arr[minInd])
minInd = i;
return minInd;
}
// A utility function that returns
// index of maximum value in arr
function getMax(arr)
{
var maxInd = 0;
for (i = 1; i < N; i++)
if (arr[i] > arr[maxInd])
maxInd = i;
return maxInd;
}
// A utility function to return minimum of 2 values
function minOf2(x , y)
{
return (x < y) ? x: y;
}
// amount[p] indicates the net amount
// to be credited/debited to/from person 'p'
// If amount[p] is positive, then
// i'th person will amount[i]
// If amount[p] is negative, then
// i'th person will give -amount[i]
function minCashFlowRec(amount)
{
// Find the indexes of minimum and
// maximum values in amount
// amount[mxCredit] indicates the maximum amount
// to be given (or credited) to any person .
// And amount[mxDebit] indicates the maximum amount
// to be taken(or debited) from any person.
// So if there is a positive value in amount,
// then there must be a negative value
var mxCredit = getMax(amount), mxDebit = getMin(amount);
// If both amounts are 0, then
// all amounts are settled
if (amount[mxCredit] == 0 && amount[mxDebit] == 0)
return;
// Find the minimum of two amounts
var min = minOf2(-amount[mxDebit], amount[mxCredit]);
amount[mxCredit] -= min;
amount[mxDebit] += min;
// If minimum is the maximum amount to be
document.write("<br>Person " + mxDebit + " pays " + min
+ " to " + "Person " + mxCredit);
// Recur for the amount array.
// Note that it is guaranteed that
// the recursion would terminate
// as either amount[mxCredit] or
// amount[mxDebit] becomes 0
minCashFlowRec(amount);
}
// Given a set of persons as graph
// where graph[i][j] indicates
// the amount that person i needs to
// pay person j, this function
// finds and prints the minimum
// cash flow to settle all debts.
function minCashFlow(graph)
{
// Create an array amount,
// initialize all value in it as 0.
var amount=Array.from({length: N}, (_, i) => 0);
// Calculate the net amount to
// be paid to person 'p', and
// stores it in amount[p]. The
// value of amount[p] can be
// calculated by subtracting
// debts of 'p' from credits of 'p'
for (p = 0; p < N; p++)
for (i = 0; i < N; i++)
amount[p] += (graph[i][p] - graph[p][i]);
minCashFlowRec(amount);
}
// Driver code
// graph[i][j] indicates the amount
// that person i needs to pay person j
var graph = [ [0, 1000, 2000],
[0, 0, 5000],
[0, 0, 0]];
// Print the solution
minCashFlow(graph);
// This code is contributed by Amit Katiyar
</script>
Producción:
Person 1 pays 4000 to Person 2 Person 0 pays 3000 to Person 2
Paradigma Algorítmico: Codicioso
Tiempo Complejidad: O(N 2 ) donde N es el número de personas.
Este artículo es una contribución de Gaurav . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA