algorithm - Balancing collective expenses between multiple actors -


suppose 3 persons have contributed expenses of trip: adam has paid hotel, $150, bob pays gas, $60, , charlie provides food, $120. after trip want balance expenses.

the easy solution each expense split between 3 persons , individually paid other participants 1 purchased in first place.

naturally, if adam owes $20 bob , bob owes $50 adam, it's equivalent bob owing $30 adam. continuing logic, bob owes $30 adam , $20 charlie, , charlie owes $10 adam.

here's catch: this solution not optimal. number of transactions can reduced. there amount of $10 first paid bob charlie , charlie adam. instead, bob add $10 sum paying adam.

in end, bob pays $10 charlie , $40 adam. has covered expenses equal amount of $110.

my questions are:

  • when goal find way expensens balanced absolute minimum amount of transactions, general solution problem n actors? traversing paths owing owed can become computationally expensive, it's not trivial.

  • can np-complete problem reduced problem?

  • is there well-known name problem?

say c people have paid more share (creditors), , d people less share (debtors). since per definition, solution optimal if implies minimum number of transactions, ideal case every debtor needs make single transfer (they have make @ least one). question then, can x1, money owed creditor 1, obtained exact sum of amounts owed? can x2 obtained exact sum of remaining amounts? , on until xc. in sense problem related subset sum problem, stated (a bit tersely) n.m..


Comments

Post a Comment

Popular posts from this blog

jquery - Invalid Assignment Left-Hand Side -

i trying assign class tag via jquery, resulting in error through firebug says "invalid assignment left-hand side" on fourth line below. <cfoutput> $('.pngfix a').each(function(index) { var hreflink = $(this).attr("href"); if (hreflink.tolowercase() = '../audio.cfm') { $(this).addclass('audioimg'); } }); </cfoutput> looking around online, looks syntax problem, don't seem see it... any tips? thanks if (hreflink.tolowercase() = '../audio.cfm') that attempts assign value, rather check equality. change = operator == .
Read more

java - Play! framework 2.0: How to display multiple image? -

i need display gallery of photos. here template: @(photos: list[photo]) @title = { <bold>gallery</bold> } @main(title,"photo"){ <ul class="thumbnails"> @for(photo <- photos) { <li class="span3"> <a href="#" class="thumbnail"> <img src="@photo.path" alt=""> </a> </li> } </ul> } and here controller method: public static result getphotos() { return ok(views.html.photo.gallery.render(photo.get())); } and here photo bean : @entity public class photo extends model { @id public long id; @required public string label; public string path; public photo(string path, string label) { this.path = path; this.label = label; } private static finder<long, photo> find = new finder<long, photo>( long.class, photo.class); public static list<phot...
Read more

gmail - Is there any documentation for read-only access to the Google Contacts API? -

i want read-only access user's google contacts. there stackoverflow member wanted this, , received following answer : yes, there is, use https://www.googleapis.com/auth/contacts.readonly scope , "view contacts". this exchange reference read-only access google contacts can find using google. simply using access token obtained attempt read usual google contacts api (i.e. https://www.google.com/m8/feeds ) fails insufficient permissions. similarly, using google contacts api on new target fails 404 errors (for example https://www.googleapis.com/auth/contacts.readonly/default/full ). is there documentation anywhere on how use api, or permissible way access google contacts api full read-write access?
Read more