Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Say some 20 people go to a shop and everyone buys something. When it comes to paying, 5 of them pay the complete amount of 10,000$ split unequally between them.

Since everyone bought different things they all owe different amounts to the payers. Now there are multiple ways the payers can clear the balances with the payees precisely 20 to the power 20.

My question is on what technical basis should the payers and payees contact each other for clearance? All the solutions can not be equally good, or are they?

One of the ways of clearing would be to find payers and payees with equal amount so that they can cancel out each other thus reducing the total number of transfers.

UPDATE:

  1. People can transfer arbitrary amounts to anyone.
  2. Minimizing total number of transfers is the main goal.
  3. A payee can not pay an amount greater that what he owes and become secondary payer.
  4. The output should be a list of suggested transfers. A suggested transfer would look like this {FromUser: a, ToUser: b, ClearanceAmount: 100}
  5. The payers don't know who holds their debt.
  6. The payees debt can be split across multiple payers.
  7. The payees knows how much each payer paid from the total amount.
share|improve this question
2  
The question is not clear. Are you trying to optimize something here? Minimum number of transfers? Is there any limit to what people can pay each other (can they exchange arbitrary amounts of many with perfect precision)? –  psr Mar 28 '13 at 17:47
    
Possible solution, if you just want to get the balance correct and are sure that all items were recorded accurately: create one account, let everyone pay into that account the amount his items are worth/retrieve the amount they paid to much. The account will have an amount of zero left, if everything was done correctly. If not, an error occured. If that does not solve it: the question is not clear, as mentionend by psr. –  Thomas Mar 28 '13 at 17:50
    
@psr. I have updated the question with some more details. –  Tushar Mathur Mar 28 '13 at 17:51
2  
I think the question is still under-specified. Can the payers communicate with each other? Do they trust each other? Is there a cost to communication? Do you assume that all debtors (payees really isn't the right term) will pay what they owe? –  William Shakespeare Mar 28 '13 at 17:53
1  
@Caleb, Payers CAN communicate, they do trust each other, no cost to communication and everyone pays what they owe. –  Tushar Mathur Mar 28 '13 at 17:59

1 Answer 1

up vote 2 down vote accepted

This is a generalization of the subset sum problem.

In the simple case, where there are two payers, it is identical to the subset sum problem. Either there is subset of debts exactly equal to the amount payed by one payer, or one payment must be split between the two payers.

The subset sum problem is NP complete, so there is no "fast" solution.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.