algorithm to determine minimum payments amongst a group

The Problem

I was recently asked to calculate the money owed amongst a group of people who went on a trip together and came upon an interesting problem: given that you know the amounts that each person owes another, what is a general algorithm to consolidate the debts between people so that only the minimum number of payments needs to be made? Take this as an example:

Mike owes John 100
John owes Rachel 200
Mike owes Rachel 400

We can remove a payment between Mike and John by reformulating the debts like this:

Mike owes John 0
John owes Rachel 100
Mike owes Rachel 500

I did the math by hand since it was easy enough, but then the programmer in me was itching to figure out a general algorithm to do it for an arbitrarily large group. This seems like a graph algorithm to me, so I'll reformulate this as a graph:

Viewed as a Graph

The vertices are the people in the group
The edges are directed and weighted by the amount owed. For example, an edge from Mike to Rachel with weight 500 means that Mike owes Rachel 500.
Constraint: the net sum of weights for each node must remain unchanged.
The goal is to find a graph with the minimum number of edges that still satisfy the constraint.

Solution

It does not suffice to just figure out the receivers and givers. While I think this strategy is on the right track it also does not ensure an algorithm to find the least possible amount of payments.

For Example,

Person A owes 25
Person B owes 50
Person C owes 75
Person D is owed 100
Person E is owed 50

While it is obvious that this can be done in 3 pays (A and C to D, B to E). I can't think of an efficient algorithm that will satisfy this for all problem sets.

Better Example,

Person A owes 10
Person B owes 49
Person C owes 50
Person D owes 65
Person E is owed 75
Person F is owed 99

If we took the greedy approach of having person D pay to F we would wind up with a sub-optimal solution as opposed to the optimal(A&D to E, B&C to F).

This problem has a lot of similarity with the Bin Packing Problem which has been proven to be NP-hard. The only difference being that we have multiple bins of varying sizes and the condition that the total space in all bins is equal to the total size of all items. This leads me to believe that the problem is likely NP-hard but with the added constraints it may be possible to solve in polynomially time.