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