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 debitedamount. */
private static int getMaximumDRIdx(int[] amount) {
if(amount.length<=1) {
return 0;
}
int maxDRIdx = 0;
int min = amount[0];
int temp = 0;
for (inti = 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 (inti = 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[] = newint[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 (intperson = 0; person < row; person++) {
for (intj = 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 (inti : 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