2009-06-10 3 views
11

Non vedo l'ora di un algoritmo per il problema seguente.Algoritmo per condividere/regolare le spese tra un gruppo

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. :)

+2

Questo è un compito a casa? – Glen

+1

suona come un "viaggio di golf". – Cheeso

+0

Beh .. Sono solo curioso di sistemare le mie spese con il mio gruppo di amici .. Semplicemente agendo in modo intelligente per fare qualcosa di diverso dall'eccellenza. Nessun compito a casa comunque. :) – Guru

risposta

4

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".

+2

Penso che significhi ordinare prima per quantità spesa può minimizzare il numero di transazioni di pagamento, sebbene ciò non sia specificato come requisito –

+0

Ho pensato che ci sarebbe stato un altro modo migliore per farlo. Per riassumere, 1. Trovare la spesa totale e le spese per capo. 2. Trova 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 esauriscono le quantità. Passa al successivo + più grande numero. O c'è un modo migliore di fare? Sono solo curioso. :) – Guru

10

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

+0

Questa è una buona soluzione (suggerita da "Pax "). Il problema con me è che non ho intenzione di limitare gli utenti a tre. E la soluzione suggerita da "jwoolard" è proprio quella puntata già. Sarò felice di adottarlo. :) – Guru

+0

Basta essere consapevoli del fatto che non è un'impresa facile ottenere il minimo assoluto - devi fondamentalmente guardare l'intero spazio di ricerca. La risposta accettata in quell'altra domanda ti darà un'ottima risposta, ma ci sono condizioni limite che significano che non è il minimo (l'ho definito il migliore in termini di bang-per-buck). – paxdiablo

0

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; 
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

+0

+1. molto interessante. Sembra essere promettente. Una volta ho costruito un'appspot su Python (non è stato completato con successo). Quindi, hai usato quale metodo? quale algoritmo? il mantenimento del libro a doppia entrata? – Guru

+0

In realtà è iniziato come progetto semestrale per la lezione. Quindi ho dovuto "inventare" l'algoritmo. È piuttosto difficile cercare soluzioni esistenti, perché non conosco i termini. Hai qualche suggerimento per ulteriori ricerche? –

+0

Descrizione del mio algoritmo: Ho per ogni membro il suo saldo (più o meno). Ho un algoritmo di base che lo risolve con le transazioni N-1: ordina i membri in base al saldo e quello con il saldo più basso invia denaro al prossimo e così via. Questo algoritmo può essere migliorato - cerco di trovare due coppie di persone che si sistemano solo con una transazione. Quindi cerco le triple dal resto e così via. Con ciascuno di questi sottogruppi, utilizzo l'algoritmo di base. Ma le transazioni sono risparmiate. Quindi il caso peggiore sono le transazioni N-1, ma di solito meno. –

1

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.

enter image description here

0

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.