Zahlen Sie gemeinsam das Rechnungsproblem

Es sind Personen an einem Tisch. Die te Person muss Dollar bezahlen . $n$ $i$ $p_i$

Einige Leute haben nicht die richtigen Rechnungen, um genau zu bezahlen , deshalb haben sie den folgenden Algorithmus. $p_i$

Zunächst legt jeder einen Teil seines Geldes auf den Tisch. Dann nimmt jede Person das Geld zurück, das sie überbezahlt hat.

Die Banknoten haben eine feste Stückelung (nicht Bestandteil der Eingabe).

Ein Beispiel: Angenommen, es gibt zwei Personen, Alice und Bob. Alice schuldet 5 Dollar und hat fünf 1- Dollar- Scheine. Bob schuldet 2 Dollar und hat eine 5- Dollar- Rechnung. Nachdem Alice und Bob ihr gesamtes Geld auf den Tisch gelegt haben, nimmt Bob 3 Dollar zurück und alle sind glücklich.

Natürlich gibt es Zeiten, in denen man nicht sein ganzes Geld auf den Tisch legen muss. Wenn Alice zum Beispiel tausend 1- Dollar- Scheine hatte, muss sie nicht alle auf den Tisch legen und dann die meisten zurücknehmen.

Ich möchte einen Algorithmus mit folgenden Eigenschaften finden:

Die Eingabe gibt die Anzahl der Personen an, wie viel jede Person schuldet und wie viele Scheine jeder Stückelung jede Person hat.
Der Algorithmus teilt jeder Person mit, welche Rechnungen in der ersten Runde auf den Tisch gelegt werden sollen.
Der Algorithmus teilt jeder Person mit, welche Rechnungen in der zweiten Runde vom Tisch zu entfernen sind.
Die Anzahl der auf den Tisch gelegten Banknoten + die Anzahl der von dem Tisch entfernten Banknoten wird minimiert.

Wenn es keine praktikable Lösung gibt, gibt der Algorithmus nur einen Fehler zurück.

algorithms optimization Chao Xu
quelle

Sind die Stückelungen der Scheine im Voraus festgelegt (sagen wir, die amerikanischen Stückelungen $ 1, $ 2, $ 5, $ 10, $ 20, $ 50 und $ 100) oder Teil der Eingabe? Mit anderen Worten, muss der Algorithmus die Möglichkeit berücksichtigen, dass Mephistopheles drei 7- Dollar- Scheine, einen 13- Dollar- Schein und fünfzehn 4- Dollar- Scheine hat ?

JeffE

Die Rechnungen sind fixiert. In diesem Fall kann ich die Teilmengen nicht reduzieren und beweisen, dass es NP-schwer ist. Ich werde es bearbeiten.

Chao Xu

Sie benötigen eine Möglichkeit, 4/5 als einzelne Optimierung auszudrücken. Es ist nicht möglich, für diese beiden unabhängigen Bedingungen zu optimieren. Ich weiß, was Sie beabsichtigen, ich hatte zuvor ein ähnliches Problem, aber Sie müssen genau quantifizieren, was es bedeutet, für beide Bedingungen zu optimieren.

edA-qa mort-ora-y

Ich denke, es wäre besser, als Ausgangspunkt anzunehmen, dass entweder jeder die Rechnung genau bezahlt oder der Algorithmus einfach einen Fehler meldet.

JeffE

Was genau ist hier die Frage, gibt es Komplexitätsanforderungen? Einen naiven Algorithmus zu schreiben scheint trivial, oder vermisse ich etwas?

Stéphane Gimenez

Antworten:

Wenn Sie das Problem auf eine etwas andere (aber äquivalente) Weise wiederholen, wird ein Algorithmus offensichtlicher:

Es sind Parteien beteiligt: Personen und ein Restaurant. Lassen Sie die Menge des Geldes Partei sollte nach dem Essen fertig ist und bezahlt. Zum Beispiel, wenn Alice 36 Dollar hat und 25 Dollar schuldet , Bob 12 Dollar hat und 11 Dollar schuldet und Carl 30 Dollar hat und 25 schuldet , sagen wir, dass das Restaurant ist und Folgendes hat: $n$ $n-1$ $p_i$ $i$ $p_0$

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

Das heißt, wenn das Essen vorbei ist, sollte das Restaurant 61 Dollar haben , Alice sollte 11 Dollar haben , Bob sollte 1 Dollar haben und Carl sollte 5 Dollar haben .

Nun lassen enumerate alle der Rechnungen beteiligt. Beispielsweise: $b$ $m$

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

Die Stückelung der Scheine spielt keine Rolle, aber ich habe für dieses Beispiel die Stückelung der US-Papierwährung gewählt, weil sie vertraut ist.

Wir suchen die Anzahl der Rechnungen , die den Besitzer wechseln zu minimieren, so dass wir ein „Kosten“ mit der Person in Verbindung mit Rechnung verlassen unter Verwendung eines Matrix . Einträge von 0 in dieser Matrix geben an, mit welchen Rechnungen jede Partei beginnt ( für alle da das Restaurant ohne Rechnungen beginnt). $i$ $j$ $\{0,1\}$ $C$ $C_{0,j} = 0$ $j$

Fortsetzung unseres Beispiels:

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]$

zeigt an, dass Alice mit gestartet $ 1 $ 5, $ 10, $ Bob begann mit 20, $ 1 $ 1 $ 5, $ 5, und Carl begann mit $ 10 und $ 20.

Auch hier ist das Ziel, die Anzahl der Geldscheine, die den Besitzer wechseln, zu minimieren. Mit anderen Worten:

\begin{aligned} Minimieren: & \sum_{ich = 0}^{n - 1} \sum_{j = 0}^{m - 1} C_{ich, j} x_{ich, j} \\ unterliegen: & \sum_{ich = 0}^{n - 1} x_{ich, j} = 1 zum 0 \leq j < m, \\ \sum_{j = 0}^{m - 1} x_{ich, j} b_{j} = p_{ich} zum 0 \leq ich < n, \\ und & x_{ich, 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}$

Die erste Einschränkung besagt, dass die Lösung nur einer Partei eine bestimmte Rechnung zuweisen kann, und die zweite stellt sicher, dass jeder den entsprechenden Betrag zahlt.

Dies ist das 0,1 INTEGER PROGRAMMING-Problem und ist NP-vollständig (siehe [ Karp 1972 ]). Die Wikipedia-Seite über lineare Programmierung enthält Informationen zu verschiedenen Algorithmen, die für diese Art von Problemen verwendet werden können.

Es gibt möglicherweise mehrere optimale Lösungen. Die erste Lösung für das Beispiel, das ich mir ausgedacht habe, war:

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]$

was bedeutet , Alice zahlt genau $ 5 und $ 20, Bob genau zahlt $ 1 $ 5 und $ 5, und Carl viel bezahlt $ 10 und $ 20 und dann entfernt einen $ 5 aus der Tabelle.

Ich habe auch das Mixed Integer Linear Program-Modul des Sage Math- Systems verwendet, das die Möglichkeit bietet, verschiedene Solver-Backends ( GLPK , COIN , CPLEX oder Gurobi ) zu verwenden. Die erste Lösung war

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]$

Das ist fast das Gleiche, außer dass Carl die "anderen" $ 5 nahm, die Bob auf den Tisch legte.

$C$ $x$

Identifizieren Sie eine Untergruppe von Personen, die den reduzierten Gesamtbetrag bezahlen können? Oder vielleicht eine Untergruppe von Leuten, die noch die gesamte Rechnung bezahlen könnten, dh sie bezahlen für ihren Freund.

Ihre abschließende Aussage lässt den Anschein erwecken, dass Sie an dem Fall interessiert sind, dass die Nennwerte der Scheine festgelegt sind. Dies ändert jedoch nichts am Problem.

$O(1)$

David
quelle

Dass sich dieses Problem als IP ausdrücken lässt, war (fast?) Klar; aber wie gut ist diese lösung Können IPs des erstellten Formulars effizient gelöst werden? Wenn nicht, gibt es einen schnelleren Algorithmus?

Raphael

Es gibt eine kondensiertere Form dieses IP, indem eine Variable für die Anzahl der Banknoten einer bestimmten Stückelung als eine Variable von 0,1 verwendet wird. Feste Nennwerte ändern die Komplexität geringfügig. Wenn auch die Anzahl der Personen festgelegt ist, kann sie der Lenstra-Algorithmus in polynomieller Zeit lösen.

Chao Xu

-2

Einige grundlegende Starts könnten sicherlich darin bestehen, die kleinsten verfügbaren Rechnungen einzuschließen, um den Gesamtbetrag der Rechnung zu erreichen. Wenn Sie keine 2- Dollar- Rechnungen zulassen möchten, könnte jede Person einfach die größte Rechnung, die sie nehmen kann, aus dem Pool entfernen und würde relativ schnell dorthin gelangen. Die 2- Dollar- Rechnung wirft das weg, da sie sich nicht gut in die anderen Konfessionen aufteilt und das Problem erheblich kompliziert. Es gibt sicherlich auch eine Reihe anderer Optimierungen, die vorgenommen werden könnten, um festzustellen, ob in Runde 1 weitere Mittel hinzugefügt werden müssen (wenn beispielsweise die Gesamtzahl von 1- Dollar- Scheinen jemals ausreicht, um die Rechnung zu decken, dann alle können aufhören einzusteigen, es sei denn, sie haben noch nicht genug für ihre Rechnung eingezahlt).

AJ Henderson
quelle