Newsgroup: it.comp.www.php
Titolo: [teorico] Algoritmo per divisione spese

Ciao a tutti, e buone feste! :-)
 
  Scusate la domanda forse OT, spero mi perdonerete. :-)
 
  Sto realizzando (in PHP) un sistema di gestione di un bene in
multiproprieta', dove due soci elencheranno le operazioni effettuate e,
per quanto legato alla questione, eventuali spese o ricavi sostenuti
personalmente.
 
  Ho studiato un algoritmo generale ma temo che, per quanto mi sembri
semplice ed efficiente, non sia il migliore possibile, per cui chiedo a
voi se ci sono soluzioni piu' eleganti.
 
  Spero di spiegarmi bene. L'accrocchio che sto progettando dovrebbe, al
momento di fare il bilancio tra soci, dire: "tizio deve dare a caio tot
euro" in modo da pareggiare i conti.
 
  Dato N (intero) numero dei soci, calcolo prima il bilancio generale
(totale T, cioe' (profitti-perdite)) e, dividendo per N, la media M
di euro che tutti a fine bilancio avranno in cassa (come profitto o
perdita).
 
  Prendo poi l'array N bilanci personali (X1, X2..., Xn), uno per socio,
ordinato dal piu' "ricco" (quello che ha incassato di piu' oppure, in
caso di sole spese, quello che ha speso di meno) al piu' povero e, dal
primo, faccio pagare al successivo socio quanto serve per pareggiare
i conti ( abs(X1-M) ), scorrendo l'array fino all'ultimo. Cosi', al primo
passaggio, X1 si trova ad avere "in cassa" esattamente quanto deve,
spostando l'eccesso a X2 e cosi' via. Dopo (N-1) passaggi ho scorso
tutto l'array e i conti sono a posto. Faccio un caso pratico, forse si
capisce meglio. Quattro soci (N=4):
 
X1 = -20 euro (ha cioe' speso 20 euro)
X2 = +50 euro (ha incassato 50 euro)
X3 = +30 euro
X4 = -20 euro
 
T=(-20+50+30-20)=40
 
M=(40/4)=10
 
Array ordinato: {X2, X3, X1, X4}
 
X2 da' a X3 (50-10), cioe' 40 euro
X3 da' a X1 60 euro (avendo preso i 40 da x1, ha in cassa 70 euro)
X1 da' a X4 20 euro (dai 40 che aveva)
 
  Alla fine hanno tutti 20 euro. :-D
 
  Funziona tutto, mi pare, ma questo passar soldi a cascata da X1 a Xn
e' un po' complicato... prima di implementarlo, sapete ci sono modi
migliori, a portata di grande inesperto, per risolvere il problema?
 
  Grazie e ancora auguri a tutti, :-)
 
 
-- 
Gianfranco Bertozzi

 migliori, a portata di grande inesperto, per risolvere il problema?
 
Beh, per un modo veramente ottimale bisognerebbe far ricorso appunto all'
ottimizzazione.
 
 
http://math.unipa.it/~tegolo/MTDS/MTDS_17.pdf
 
 
Leonardo
 
-- 
 
Then felt I like some watcher of the skies, when a new planet swims into his ken;
Or like stout Cortez when with eagle eyes, he star'd at the Pacific; and all his men
Look'd at each other with a wild surmise - silent, upon a peak in Darien.

 impostare un problema di ricerca operativa - potrebbe essere questo:
 
  Ho capito, credo. :-)
 
  Come dici tu, per un numero di soci > 2 lo svantaggio di questo
approccio e' che ogni socio puo' spalmare il suo credito su piu'
persone, col rischio di aumentare anziche' diminuire il numero di
passaggi di denaro. Lo svantaggio del mio e' che crea questa "onda"
aumentando la quantita' di denaro che circola da uno all'altro.
 
  Visto lo scopo pratico del sistema, non credo sia utile mettersi ad
ottimizzare ulteriormente, scegliero' uno dei due approcci o niente
del tutto, in base a quel che dira' il committente. Mal che vada si
metteranno d'accordo tra loro e faranno probabilmente prima. ;-)
 
  Grazie anche per le indicazioni e il link. Ho imparato parecchie
cose nuove, anche se molti concetti e le formule sono oltre le mie
competenze. Come ho detto sono un principiante, anche se cerco di
migliorare. :-)
 
  Un saluto e buon natale a tutti,
 
-- 
Gianfranco Bertozzi