Consigli su struttura dati e algoritmo


#1

Buongiorno a tutti,
ho in mente un problema non collegato alle Olimpiadi (per lo meno io non ho mai trovato un esercizio simile) ma che potrebbe essere interessante risolvere.

Il problema è comune e provo a spiegarlo con un esempio:
4 amici sono appassionati di calcio e si condividono le figurine. Ad esempio FB può comprare delle figurine e condividerle con tutti. Il giorno dopo AC fa lo stesso. La sera DI esce con SR, compra delle le figurine che vengono suddivise solo fra loro due. E così via.
Alla fine, ovviamente, ci sarà qualcuno che ha pagato più figurine di quante ne abbia, qualcun altro meno.

Secondo voi qual è la struttura dati e l’algoritmo più adatto per restituire i soldi nel minore numero di “transazioni” possibili? (se FB paga 10€ e regala tutte le figurine ad AC e AC fa lo stesso con DI, alla fine DI dovrà restituire 10€ a FB senza passare da AC).

Spero di essere stato abbastanza chiaro.
Grazie e tutti e buon ragionamento.


#2

È un problema noto, e non si conosce un algoritmo che trovi il minor numero di transazioni in tempo polinomiale.

Questo paper (22 pagine) descrive il problema.

Quest’altro paper (6 pagine) sempre dello stesso autore ma molto più corto mostra alcuni “casi” e secondo me anche solo questo paper è sufficiente a capire l’algoritmo, il quale ha complessità O(N!) dove N è il numero di persone coinvolte.

@lukecavabarrett mi raccontò una volta di un modo per ridurre la complessità, ma solo lui sa spiegarlo! :sweat_smile:

Aggiungo che esistono diverse app per smartphone, tra le quali una piuttosto popolare è Splitwise, che fanno questo “conto” per te. Dato che il numero di persone che potresti dare in pasto all’app può ovviamente essere troppo alto (già con 20 la soluzione classica è lentissima) queste app fanno uso di euristiche per ridurre i tempi a discapito dell’ottimalità della soluzione.

Su Quora trovi una risposta dal fondatore di Splitwise che spiega come fanno.


#3

Proprio dalla scoperta di Splitwise sono partito, grazie mille per la documentazione.

Aspettiamo con ansia la spiegazione di @lukecavabarrett :joy: