Path: news.mathworks.com!not-for-mail
From: "Neal Gordon" <gordon.363@osu.edu>
Newsgroups: comp.soft-sys.matlab
Subject: Re: Simple Optimization Problem
Date: Sat, 14 Mar 2009 04:08:01 +0000 (UTC)
Organization: The Ohio State University
Lines: 66
Message-ID: <gpfaj1$im7$1@fred.mathworks.com>
References: <gpf8hd$863$1@fred.mathworks.com> <84a25b13-1e98-4886-bfa2-f1454477e057@l39g2000yqn.googlegroups.com>
Reply-To: "Neal Gordon" <gordon.363@osu.edu>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1237003681 19143 172.30.248.38 (14 Mar 2009 04:08:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 14 Mar 2009 04:08:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 607146
Xref: news.mathworks.com comp.soft-sys.matlab:524791


ImageAnalyst <imageanalyst@mailinator.com> wrote in message <84a25b13-1e98-4886-bfa2-f1454477e057@l39g2000yqn.googlegroups.com>...
> On Mar 13, 11:33=A0pm, "Neal Gordon" <gordon....@osu.edu> wrote:
> > OK, here is my question. A simple example: Say you have 4 people who each=
>  spend a certain amount.
> > Bob - $50
> > Tim - $5
> > Sal - $95
> > Jon - $200
> > Together they spent $350, so thats an average of $87.5/person.
> > Find a solution to minimize the number of transactions between the people=
>  so that everyone has spent the same amount.
> >
> > example solution
> > Tim pays Jon $82.5
> > Bob pays Jon $30
> > Bob pays Sal $7.5
> >
> > Thanks.
> > -Neal
> ---------------------------------------------------------------------------=
> ------------------
> I don't understand.  If Tim pays $5 total, or even $5 per transaction,
> then how can he spend $82.5 which is not a multiple of $5?  And in
> your example solution, not everybody has paid the same amount.  Tim
> paid $82.50, Bob paid $37.50, and Jon and Sal didn't pay(spend)
> anything.  Are you sure you're explaining this correctly?

Original amount spent:
Bob - $50
Tim - $5
Sal - $95
Jon - $200
Together, as a group, they spent $350 = 50+5+95+200, so thats an average of $87.5/person.

So, to clarify, we would like to find the quickest way for everyone in the group to have spent the same amount overall. Now, I will show the iterations with the current amount spent per person.
--iteration 0--
Bob : $50
Tim : $5
Sal : $95
Jon : $200

--iteration 1--Tim pays Jon $82.5--
Bob : $50
Tim : $5 + $82.5 = $87.5
Sal : $95
Jon : $200 - $82.5 = $117.5

iteration 2--Bob pays Jon $30--
Bob : $50 + $30 = $80
Tim : $87.5
Sal : $95
Jon : $117.5 - $30 = $87.5

iteration 3--Bob pays Sal $7.5--
Bob :  $80 + $7.5 = $87.5
Tim : $87.5
Sal : $95 - $7.5 = $87.5
Jon :  $87.5

final spending with 3 iterations(transactions):
Bob : $87.5
Tim : $87.5
Sal  : $87.5
Jon : $87.5

I hope this helps. This solution is trivial, but I am interested in the solution of 15+ people while trying to achieve less iterations than the "Number of people minus 1", which in this case is 3 obvious iterations.