[Kildyt]

#matematyka #algorytmy #programowanie

Cześć miraski!
Męczę się ostatnio z zagadnieniem sprawiedliwego podziału. Możecie mnie jakoś nakierować?

Dla uproszczenia problemu zabawimy się w lewaka.

Mamy 100 zł i chcemy je rozdać potrzebującym.
W naszej wiosce są oprócz nas trzy rodziny A, B, C z majątkiem 10zł, 10zł, 90zł.

Potrzebuję funkcji, która rozdzieli te 100zł sprawiedliwie.
Efektem powinno być: 60zł, 60zł, 90zł. (A oraz B dostały po 50zł)

Czuję się jak lamus, bo wydaje się proste :/
Macie jakieś pomysły?

[thanksforthesupport]

@Kildyt: srednia wazona

[japer]

@Kildyt: Ustal proporcję majątku do sumy majątku i pomnóż go przez pulę do rozdania.

[Darjo]

@Kildyt: slabo lewacki algorytm, czemu nie zabral C tak z 50 zl najmniej?

[A.....k]

@Kildyt: To wygląda na problem planisty systemu operacyjnego. Dlaczego powinno być 60-60-90? Czy któraś rodzina zyska na tym na tyle, by się zrealizować? A czy jak dasz 100 temu, który ma najwięcej to czy będzie tak źle? Albo co jeśli dasz wszystkim po równo? Brakuje kryteriów lub jest to problem planisty.

[Kildyt]

@Analityk kryterium jest takie aby w efekcie, różnicy pomiędzy elementami były jak najmniejsze. Rodzina nie może mieć mniej niż miała na początku.

[1.....p]

@Kildyt: Celem jest minimalizacja max(f) - min(f)

Załóżmy dla uproszczenia, że f(x) >= 0
Idealnie max(f) - min(f) = 0, spróbujmy więc rozdać pieniądze tak, aby każdy miał identyczną wartość.

Nazwijmy zbiór wartości, które przyjmuje funkcja

[Kildyt]

@1080p Widzę jeden problem w sytuacji, gdy mamy więcej niż jedną "dużą" liczbę w zbiorze.
np.
S = [200, 0, 150]
Z = 100

W kroku II.b) weźmiemy pod uwagę wartość '150', co jest

[1.....p]

@Kildyt: a gdyby tak ignorowac liczby > Z?

[Angsoc]

Taktyk

[kjomputken]

Taktyk

[Kildyt]

@1080p nic z tego :/ Próbowałem na wiele sposobów i nadal nic.

[Kildyt]

Rozwiązałem problem (mam nadzieję). Algorytm nie jest zbyt wydajny, ale działa. Kiedyś się poprawi ( ͡° ͜ʖ ͡°)

Po krótce: zakładamy, że każda "komórka" (wartość w zbiorze) dostaje równą część. Komórki, których wartość zostałaby zmniejszona, zgłaszają to, co powoduje przeliczenie wartości. No i tak do końca.

Dla zainteresowanych kod w