Thumbnail Split the Bill

Door: Thijs Zumbrink
10-12-2010 14:58

Gisteren heb ik een ideetje uitgewerkt waar ik een paar dagen mee rond had gelopen. Een handig programmaatje waarmee je een (stapel) rekening(en) kunt verdelen over een groepje mensen. Dat kan handig zijn voor bijvoorbeeld inkopen voor een diner waarbij een groep mensen aanwezig is die de helft niet lust, en een andere groep die misschien vegatarier is. Er zijn natuurlijk ook nog andere voorbeelden die je zelf mag bedenken. Ik werd aangespoord door Sinterklaasinkopen met Froukje in Den Bosch. We hebben allerlei dingen gekocht, en dankzij dit programma weet ik precies waar ik aan toe ben! (Ik krijg nog geld van je! :P)

Je kunt het zelf uitproberen op http://split.schalpoen.nl/. De interface is expres heel lelijk gelaten, het gaat vooralsnog om de functionaliteit. In de interface kun je personen invoeren, en wanneer er minimaal 1 persoon ingevoerd is kun je betalingen invoeren. Zo'n betaling heeft een aantal kenmerken, waaronder natuurlijk het bedrag, de betaler, en de personen op wie de betaling allemaal toepassing heeft (wie gebruik maakt van de aankoop). Als alles ingevoerd is klik je onderin op "Calculate!" en het programma doet zijn werk. In het scherm dat daarop volgt zie je wie allemaal welke bedragen moet betalen aan elkaar. Zie je niets? Dan "is het goed zo."

Er wordt overigens geen informatie permanent opgeslagen, dus je hoeft niet bang te zijn voor spionage! Als je interesse hebt mag je de sourcecode hebben.

Hoe werkt het? (Je mag hier afhaken.) Er wordt gebruik gemaakt van een zogenaamd flow netwerk. Dit kun je zien als een stelsel van pijpen waar water doorheen kan stromen van de Source naar de Sink. Het doel is om de capaciteiten van de pijpen optimaal te benutten. Dit probleem wordt in de informatica het Max Flow / Min Cut probleem genoemd. Het wordt veel gebruikt voor allerlei soorten netwerken, bijvoorbeeld in de logistieke sector of om netwerkverkeer op het internet te regelen. Een hoop problemen (zoals het split-the-bill probleem, maar denk ook aan planning en matching) kunnen worden geformuleerd als flow probleem.

Geplaatste afbeelding

Bovenstaande afbeelding laat het netwerk zien dat ik geimplementeerd heb. Aan de linker kant zie je de Source S, aan de rechter kant de Sink T. Dat geeft de richting van de geldstroom aan. De groep A = {a1, a2, ..., an} zijn mensen die nog geld moeten betalen. De groep B = {b1, b2, ..., bm} zijn mensen die nog geld moeten ontvangen. De verbindingen tussen de betalers en ontvangers hebben allen oneindige capaciteit. De capaciteiten C tussen S en A, alsmede tussen B en T, bepalen dat de betalingen uiteindelijk kloppen. C wordt berekend als (al het geld dat je had moeten betalen) - (al het geld dat je betaald hebt). Als dit negatief is kom je in A, anders in B. Alles dat resteert is het Max Flow probleem oplossen (ik gebruik het algoritme van Edmonds-Karp vanwege diens eenvoud, maar elk flow algoritme kan gebruikt worden). Als antwoord lezen we de resulterende flow tussen A en B uit.

Reacties
Log in of registreer om reacties te plaatsen.
Thijs Zumbrink, 10-12-2010 15:27:
Ik kan trouwens wel een zekere vader bedenken die de source code wil zien, een app ervan wil maken, en vervolgens slapend rijk worden!