Algoritmo per condividere/regolare le spese tra un gruppo

Question

Non vedo l'ora di un algoritmo per il problema seguente.

Problema: ci sarà un gruppo di persone che si devono dei soldi o nessuno. Ora, ho bisogno di un algoritmo (il migliore e accurato) per regolare le spese tra questo gruppo.

Person AmtSpent 
------ --------- 
A  400 
B  1000 
C  100 
Total 1500 

Ora, la spesa per persona è 1500/3 = 500. Significato B per dare A 100. B per dare C 400. Lo so, lo può iniziare con il minor spesa e lavorare in avanti.

Qualcuno può indicarmi il migliore se lo avete.

Grazie in anticipo.

Per riassumere, 1. Trovare la spesa totale e le spese per capo.
2. Individuare l'importo dovuto o in sospeso (-ve indica in sospeso).
3. Iniziare con la quantità minima + ve. Assegnarlo alla quantità -ve.
4. Continuare a ripetere il punto 3, finché non si esaurisce la quantità.
s. Passa al successivo + più grande numero. Continua a ripetere 3 & 4 finché non ci sono + ve numeri.

Oppure c'è un modo migliore di fare? Sono solo curioso. :)

Answer 1

L'hai già descritto. Somma tutte le spese (1500 nel tuo caso), dividi per il numero di persone che condividono la spesa (500). Per ogni individuo, detrarre i contributi che la persona ha fatto dalla singola azione (per la persona A, dedurre 400 da 500). Il risultato è la rete che la persona "deve" al pool centrale. Se il numero è negativo per qualsiasi persona, la piscina centrale "deve" la persona.

Perché hai già descritto la soluzione, non so cosa stai chiedendo. Forse stai provando a risolvere il problema senza il pool centrale, la "banca"?

Inoltre, non so cosa intendi per "iniziare con l'importo minimo speso e lavorare avanti".

Answer 2

Il modo migliore per tornare allo stato zero (numero minimo di transazioni) è stato coperto in questa domanda here.

Answer 3

Semplice, come si fa nel testo:

spese torna a essere pagato da tutti nella matrice originale. Valori negativi: questa persona torna indietro

Basta dare tutto ciò che devi al prossimo in linea e poi abbandonare. Se ne ottieni qualcuno, aspetta solo il secondo round. Al termine, invertire l'intera cosa. Dopo questi due round, tutti hanno pagato lo stesso importo.

procedure SettleDepth(Expenses: array of double); 
var 
    i: Integer; 
    s: double; 
begin 
    //Sum all amounts and divide by number of people 
    // O(n) 
    s := 0.0; 
    for i := Low(Expenses) to High(Expenses) do 
    s := s + Expenses[i]; 

    s := s/(High(Expenses) - Low(Expenses)); 

    // Inplace Change to owed amount 
    // and hand on what you owe 
    // drop out if your even 
    for i := High(Expenses) downto Low(Expenses)+1 do begin 
    Expenses[i] := s - Expenses[i]; 
    if (Expenses[i] > 0) then begin 
     Expenses[i-1] := Expenses[i-1] + Expenses[i]; 
     Expenses.Delete(i); 
    end else if (Expenses[i] = 0) then begin 
     Expenses.Delete(i); 
    end; 
    end; 

    Expenses[Low(Expenses)] := s - Expenses[Low(Expenses)]; 
    if (Expenses[Low(Expenses)] = 0) then begin 
    Expenses.Delete(Low(Expenses)); 
    end; 

    // hand on what you owe 
    for i := Low(Expenses) to High(Expenses)-1 do begin 
    if (Expenses[i] > 0) then begin 
     Expenses[i+1] := Expenses[i+1] + Expenses[i]; 
    end; 
    end; 
end; 

Answer 4

Ho creato un'app per Android che risolve questo problema. Puoi inserire le spese durante il viaggio, ti consiglia anche "chi dovrebbe pagare il prossimo". Alla fine calcola "chi deve inviare quanto a chi".Il mio algoritmo calcola il numero minimo richiesto di transazioni ed è possibile l'installazione di "tolleranza transazione" che può ridurre le transazioni ancora di più (non si cura circa $ 1 transazioni) Provalo, si chiama Settle Up:

https://market.android.com/details?id=cz.destil.settleup

Descrizione del mio algoritmo:

Ho un algoritmo di base che risolve il problema con le transazioni n-1, ma non è ottimale. Funziona così: dai pagamenti, calcolo il saldo per ogni membro. L'equilibrio è ciò che ha pagato meno quello che dovrebbe pagare. Ordino sempre più membri in base all'equilibrio. Poi prendo sempre il più povero e il più ricco e la transazione è fatta. Almeno uno di essi finisce con zero saldo ed è escluso da ulteriori calcoli. Con questo, il numero di transazioni non può essere peggiore di n-1. Inoltre riduce al minimo l'ammontare di denaro nelle transazioni. Ma non è ottimale, perché non rileva sottogruppi che possono stabilirsi internamente.

Trovare i sottogruppi che possono stabilirsi internamente è difficile. Lo risolvo generando tutte le combinazioni di membri e controllando se la somma dei saldi nel sottogruppo è uguale a zero. Comincio con coppie a 2 coppie, quindi a 3 coppie ... (n-1). Sono disponibili implementazioni di generatori combinati. Quando trovo un sottogruppo, calcolo le transazioni nel sottogruppo usando l'algoritmo di base descritto sopra. Per ogni sottogruppo trovato, viene risparmiata una transazione.

La soluzione è ottimale, ma la complessità aumenta a O (n!). Questo sembra terribile, ma il trucco è che ci sarà solo un piccolo numero di membri nella realtà. L'ho provato su Nexus One (1 Ghz procesor) ei risultati sono: fino a 10 membri: < 100 ms, 15 membri: 1 s, 18 membri: 8 s, 20 membri: 55 s. Quindi fino a 18 membri il tempo di esecuzione va bene. Una soluzione alternativa per> 15 membri può essere quella di utilizzare solo l'algoritmo di base (è veloce e corretto, ma non ottimale).

Codice sorgente:

codice sorgente è disponibile all'interno di un rapporto su un algoritmo scritto in ceco. Il codice sorgente è alla fine ed è in inglese:

http://www.settleup.info/files/master-thesis-david-vavra.pdf

Answer 5

L'idea (simile a quello che viene chiesto, ma con una torsione/usando un po 'di concetto di contabilità) è quello di utilizzare Pool account dove per ogni fattura, i membri o pagano alla piscina o ottengono dalla piscina. ad es. nell'immagine allegata sotto, le spese di Costco sono pagate dal signor P e ha bisogno di $ 93,76 da Pool e gli altri membri pagano $ 46,88 al pool.

Answer 6

ho recentemente scritto a blog post che descrive un approccio per risolvere il rimborso delle spese tra i membri di un gruppo in cui potenzialmente ognuno deve tutti gli altri, in modo tale che il numero di pagamenti necessari per risolvere i debiti è il meno possibile . Usa una formulazione di programmazione lineare. Ho anche mostrato un esempio utilizzando un piccolo pacchetto R che implementa la soluzione.