There
are a number of friends who have to give or take some amount of money from one
another. Task is to design an algorithm by which the total cash flow among all
the friends is minimized.
Approach#
The approach
is using the Greedy algorithm where
we are settling amount of one person (Debts or credits) at every step and
recurring the same for remaining n-1 persons.
First,
we will calculate the net amount for every person where net amount is obtained
by subtracting all debts (amounts to pay) from all credits (amounts to be
paid). Once net amount for every person is evaluated, find two persons with
maximum and minimum net amounts. These two persons are the most creditors and
debtors. The person with minimum of two is our first person to be settled and
removed from list.
public class MinCashFlow {
/** Recursively calling for next
transaction */
private static void calculateTheFlow(int[]
amount) {
int maxDRIdx = getMaximumDRIdx(amount);
int maxCRIdx = getMaximumCRIdx(amount);
if(amount[maxDRIdx]==0 && amount[maxCRIdx]==0) {
return;
}
int crAmount = amount[maxCRIdx];
int drAmount = amount[maxDRIdx];
int diff = crAmount + drAmount;
if(diff<0) {
System.out.println("Person "+maxDRIdx +" will pay "+ crAmount+ " rs. to pay
to "+maxCRIdx);
amount[maxCRIdx] = 0;
amount[maxDRIdx] = diff;
} else {
System.out.println("Person "+maxDRIdx +" will pay "+ Math.abs(drAmount)+ " rs. to pay
to "+maxCRIdx);
amount[maxDRIdx] = 0;
amount[maxCRIdx] = diff;
}
//printArray(amount);
calculateTheFlow(amount);
}
/** To get the maximum debited
amount. */
private static int getMaximumDRIdx(int[]
amount) {
if(amount.length<=1) {
return 0;
}
int maxDRIdx = 0;
int min = amount[0];
int temp = 0;
for (int
i = 1; i < amount.length; i++) {
if(min>(temp=Math.min(min, amount[i]))) {
maxDRIdx = i;
min = temp;
}
}
return maxDRIdx;
}
/**
* To
get the maximum credited amount.
*/
private static int getMaximumCRIdx(int[]
amount) {
if(amount.length<=1) {
return 0;
}
int maxCRIdx = 0;
int max = amount[0];
int temp = 0;
for (int
i = 1; i < amount.length; i++) {
if(max<(temp=Math.max(max, amount[i]))) {
maxCRIdx = i;
max = temp;
}
}
return maxCRIdx;
}
/** Method to to calculate the minimum cash
flow. */
private static void minCashFlow(int[][]
flowGraph) {
int row = flowGraph.length;
int col = flowGraph[0].length;
int amount[] = new
int[row];
/**
* Calculate the net amount to be paid to person, and stores it in
amount[person].
* The value of amount[person] can be calculated by subtracting
* debts of 'person' from credits of 'person'
*/
for (int
person = 0; person < row; person++) {
for (int
j = 0; j < col; j++) {
amount[person] += flowGraph[j][person] - flowGraph[person][j];
}
}
printArray(amount);
calculateTheFlow(amount);
}
/** Utility to
print an array. */
private static void printArray(int[]
amount) {
for (int
i : amount) {
System.out.print(i+" ");
}
System.out.println();
}
/** Driver method. */
public static void main(String[] args) {
/** flowGraph[i][j] indicates the amount
that person i needs to pay person j.*/
int[][] flowGraph = {{0, 2000, 3000},
{10000, 0, 6000},
{0, 0, 0},};
/** Call the function which will calculate
the cash flow. */
minCashFlow(flowGraph);
}
}
No comments:
Post a Comment