Zbiorowy problem z rachunkiem

Przy stole jest $n$ ludzi. $i$ th osoba musi zapłacić $p_i$ dolarów.

Niektórzy ludzie nie mają odpowiednich rachunków, aby zapłacić dokładnie , dlatego opracowali następujący algorytm. $p_i$

Po pierwsze, wszyscy kładą na stole część swoich pieniędzy. Następnie każda osoba odbiera nadpłacone pieniądze.

Rachunki mają ustalony zestaw nominałów (nie stanowi części danych wejściowych).

Przykład: Załóżmy, że są dwie osoby, Alice i Bob. Alice jest winna 5 USD i ma pięć rachunków za 1 USD . Bob jest winien 2 USD i ma jeden 5 USD . Po tym, jak Alice i Bob położyli wszystkie swoje pieniądze na stole, Bob zabiera 3 $ i wszyscy są szczęśliwi.

Oczywiście są chwile, w których nie trzeba odkładać wszystkich pieniędzy na stół. Na przykład, jeśli Alicja miała tysiąc rachunków za 1 USD , nie musi kłaść ich wszystkich na stole, a następnie odbierać większość z nich.

Chcę znaleźć algorytm o następujących właściwościach:

Dane wejściowe określają liczbę osób, ile każda osoba jest winna i ile rachunków każdej denominacji ma każda osoba.
Algorytm mówi każdej osobie, które rachunki należy postawić na stole w pierwszej rundzie.
Algorytm mówi każdej osobie, które rachunki należy usunąć ze stołu w drugiej rundzie.
Liczba rachunków postawionych na stole + liczba rachunków usuniętych ze stołu jest zminimalizowana.

Jeśli nie ma wykonalnego rozwiązania, algorytm po prostu zwraca błąd.

algorithms optimization

— Chao Xu
źródło

Są nominały bonów ustalonych z góry (powiedzmy do amerykańskich wyznań $ 1, $ 2, $ 5, $ 10, $ 20, $ 50 i $ 100) lub części wkładu? Innymi słowy, czy algorytm musi poradzić sobie z możliwością, że Mefistofeles ma trzy rachunki za 7 USD, rachunek za 13 USD i piętnaście rachunków za 4 USD ?

— JeffE

Rachunki są stałe. Wydaje mi się, że w takim przypadku nie mogę zmniejszyć sumy podzbioru i udowodnić, że jest to NP-Hard. Zmienię to.

— Chao Xu,

Potrzebujesz sposobu wyrażenia 4/5 jako pojedynczej optymalizacji. Nie można zoptymalizować tych dwóch niezależnych warunków. Wiem o tym, co zamierzasz, miałem wcześniej podobny problem, ale musisz dokładnie określić, co to znaczy zoptymalizować dla obu warunków.

— edA-qa mort-ora-y

Myślę, że lepiej byłoby na początku założyć, że albo wszyscy płacą rachunek dokładnie, albo algorytm po prostu zgłasza awarię.

— JeffE

Jakie jest dokładnie pytanie, czy istnieją wymagania dotyczące złożoności? Pisanie naiwnego algorytmu wydaje się trywialne, czy coś mi brakuje?

— Stéphane Gimenez

Odpowiedzi:

Jeśli ponownie rozwiążesz problem w nieco inny (ale równoważny) sposób, algorytm stanie się bardziej oczywisty:

$n$ $n-1$ $p_i$ $i$ $p_0$

$p = (61, 11, 1, 5)$

Oznacza to, że po zakończeniu posiłku restauracja powinna mieć 61 USD , Alice powinna mieć 11 USD , Bob powinien mieć 1 USD, a Carl 5 USD .

$b$ $m$

$b = (1, 5, 10, 20, 1, 1, 5, 5, 10, 20)$

Nominały rachunków nie mają znaczenia, ale dla tego przykładu wybrałem nominały papierowej waluty amerykańskiej, ponieważ są one znane.

$i$ $j$ $\{0,1\}$ $C$ $C_{0,j} = 0$ $j$

Kontynuując nasz przykład:

C = [\begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \end{array}]

$C = \left[ \begin{array}{cccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \right]$

wskazuje, że Alice zaczęło się $ 1 $ 5, $ 10 $ 20 Bob zaczął z $ 1 $ 1 $ 5, $ 5, a Carl rozpoczął z $ 10 i $ . 20

Ponownie, celem jest zminimalizowanie liczby rachunków, które zmieniają ręce. Innymi słowy:

\begin{aligned} Minimize: & \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} C_{i, j} x_{i, j} \\ subject to: & \sum_{i = 0}^{n - 1} x_{i, j} = 1 for 0 \leq j < m, \\ \sum_{j = 0}^{m - 1} x_{i, j} b_{j} = p_{i} for 0 \leq i < n, \\ and & x_{i, j} \geq 0 \end{aligned}

$\begin{align} \text{Minimize:} & \sum_{i=0}^{n-1}{\sum_{j=0}^{m-1}{C_{i,j} x_{i,j}}} \\ \text{subject to:} & \sum_{i=0}^{n-1}{x_{i,j}} = 1 \text{ for } 0 \le j \lt m, \\ & \sum_{j=0}^{m-1}{x_{i,j}b_j = p_i} \text{ for } 0 \le i \lt n, \\ \text{and} & x_{i,j} \ge 0 \end{align}$

Pierwsze ograniczenie mówi, że rozwiązanie może przypisać konkretny rachunek tylko jednej stronie, a druga gwarantuje, że wszyscy zapłacą odpowiednią kwotę.

Jest to problem z PROGRAMOWANIEM INTEGRALNYM 0,1 i jest kompletny NP (patrz [ Karp 1972 ]). Strona Wikipedii na temat programowania liniowego zawiera informacje na temat różnych algorytmów, które można zastosować w przypadku tego rodzaju problemów.

Istnieje potencjalnie wiele optymalnych rozwiązań; ręcznie pierwszym rozwiązaniem wymyślonego przeze mnie przykładu było:

x = [\begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{array}]

$x = \left[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \end{array} \right]$

co oznacza, Alicja płaci dokładnie $ 5 i $ 20 Bob płaci dokładnie $ 1 $ 5 i $ 5, a Carl overpays $ 10 i $ 20, a następnie usuwa $ 5 Z tabeli.

Użyłem również modułu Mixed Integer Linear Program systemu Sage Math , który ma możliwość korzystania z różnych backendów solvera ( GLPK , COIN , CPLEX lub Gurobi ). Pierwszym rozwiązaniem było

x = [\begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{array}]

$x = \left[ \begin{array}{cccccccccc} 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right]$

co jest prawie takie samo, z wyjątkiem tego, że Carl wziął „inne” 5 $, które Bob postawił na stole.

$C$ $x$

Zidentyfikować grupę osób, które mogą zapłacić obniżoną sumę? A może część ludzi, którzy wciąż mogą zapłacić cały rachunek, tj. Płacą za przyjaciela.

Ostatnie oświadczenie sprawia, że wydaje się, że interesuje Cię ustalenie nominałów rachunków, ale nie zmienia to problemu.

$O(1)$

— David
źródło

To, że problem ten można wyrazić, ponieważ IP było (prawie?) Jasne; ale jak dobre jest to rozwiązanie? Czy adresy IP utworzonej formy można skutecznie rozwiązać? Jeśli nie, czy istnieje szybszy algorytm?

— Raphael

Istnieje bardziej skondensowana forma tego adresu IP, posiadająca zmienną dla liczby rachunków o konkretnym nominale niż zmienna 0,1. Naprawione nominały zmieniają nieco złożoność, jeśli liczba osób jest również stała, algorytm Lenstry może rozwiązać to w czasie wielomianowym.

— Chao Xu,

-2

Z pewnością niektórymi podstawowymi początkami mogą być najmniejsze dostępne rachunki, aby osiągnąć całkowitą kwotę ogólnego rachunku. Jeśli nie chcesz pozwolić na rachunki w wysokości 2 USD , każda osoba może po prostu usunąć największy rachunek, jaki może wziąć z puli, i dotrze tam stosunkowo szybko. $ 2 Bill że rzuca się jak to nie sub-divide ładnie się do innych wyznań i znacznie komplikuje problem. Z pewnością można również przeprowadzić szereg innych optymalizacji, aby dokonać obserwacji na temat potrzeby dodania dodatkowych środków podczas pierwszej rundy (na przykład, jeśli łączna liczba rachunków o wartości 1 USD jest kiedykolwiek wystarczająca na pokrycie rachunku, wówczas wszyscy mogą przestać wkładać, chyba że nie wpłacili jeszcze wystarczającej kwoty na rachunek).

— AJ Henderson
źródło