Implementación de un algoritmo devorador ( [Enlace externo eliminado para invitados] ) para resolver este problema:



Solución:


Un ejemplo un poco más complicado


Y su solución:



Implementación:

MinCashFlow.java

package logic;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedHashMap;

public class MinCashFlow {
	private	Person[] v;	


	public Person[] getV(){
		return v;
	}
	
	public MinCashFlow(Person[] v){
		this.v = v;
	}
	
	public void minimization(){
		Arrays.sort(v, new Comparator<Person>(){
			@Override
			public int compare(Person p1, Person p2){
				return p1.getMoney()-p2.getMoney();
			}
		}
		);
		
		int i = 0;	int j = v.length-1;
		System.err.println("\n**Resultados Finales");
		do{			
			if(v[j].getMoney() > -v[i].getMoney()){
				System.out.println("" + v[i].getName() + " paga a " + v[j].getName() + " " + -v[i].getMoney() + " euros");
				v[j].setMoney(v[j].getMoney() + v[i].getMoney());
				v[i].setMoney(0);
				i++;
			}else{
				System.out.println("" + v[i].getName() + " paga a " + v[j].getName() + " " + v[j].getMoney() + " euros");
				v[i].setMoney(v[i].getMoney() + v[j].getMoney());
				v[j].setMoney(0);
				j--;
			}
		} while(!areBalanced());
	}
	
	private void showTrace(){
		for(int i=0; i<v.length; i++){
			System.err.print(v[i].getMoney() + "\t");
		}
		System.err.println();
	}
	
	public boolean areBalanced(){
		for(Person i: v){
			if(i.getMoney()!=0)	return false;
		}
		return true;
	}
}

Person.java

package logic;

public class Person {
	private int money;
	private String name;
	
	public Person(String name, int money){
		this.name = name;
		this.money = money;
	}
	
	public int getMoney() {
		return money;
	}
	public void setMoney(int money) {
		this.money = money;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	
}

Loader.java (Cargador datos E/S)

package logic;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedHashMap;

public class Loader {
	private ArrayList<String[]> lines;
	private static ArrayList<Integer> money = new ArrayList<Integer>();
	private static ArrayList<String> names = new ArrayList<String>();
	
	private int[] v;
	private LinkedHashMap<String, Integer> persons;
	
	public int[] getV(){
		return v;
	}
	
	public LinkedHashMap<String, Integer> getPersons(){
		return persons;
	}
	
	public Loader(String path) throws IOException{
		persons = new LinkedHashMap<String, Integer>();
		lines = new ArrayList<String[]>();
		fReader(path);
		
		v = new int[persons.size()];
	}
	
	public void fReader(String path) throws IOException{
		BufferedReader br = new BufferedReader(new FileReader(path));
		String line = br.readLine();
		
		int counter=0;
		System.err.println("**Computando balance de cuentas:");
		while(line != null){
			String[] splitted = line.split(" ");
			lines.add(splitted);
			
			if(!persons.containsKey(splitted[0])){
				persons.put(splitted[0], counter);
				counter++;
			}
			if(!persons.containsKey(splitted[1])){
				persons.put(splitted[1], counter);
				counter++;
			}
			
			System.out.print("" + splitted[0] + " tiene que pagar " + splitted[2] + " a " + splitted[1] + "\n");
			line = br.readLine();
		}
		
		br.close();
	}
	
	public void prepareVector(){
		for(int i=0; i<lines.size(); i++){
			v[persons.get(lines.get(i)[0])] += -Integer.parseInt(lines.get(i)[2]);
			v[persons.get(lines.get(i)[1])] += Integer.parseInt(lines.get(i)[2]);
		}
	}
	
	
	public static void main(String[] args){
		Loader l;
		try {
			l = new Loader("C:\\Users\\Esteban\\Desktop\\caso1.txt");
			l.prepareVector();

			Iterator it = l.getPersons().keySet().iterator();
			while(it.hasNext()){
				String key = (String) it.next();
				names.add(key);
			}
			
			for(int i: l.getV()){
				money.add(i);
			}
			
			
			Person[] toLoad = new Person[money.size()];
			for(int i=0; i<money.size(); i++){
				toLoad[i] = new Person(names.get(i), money.get(i));
			}

			MinCashFlow m = new MinCashFlow(toLoad);
			m.minimization();
			
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

	}
}

OUTPUT: