Sagen wir, wir haben N Anzahl von Konten mit positiven Salden B_1, ..., B_n .
Wir können eine Überweisung T(from,to,amount) vornehmen, die einen bestimmten Kontostand verschiebt.
Wir haben Kenntnis über eine optimale Verteilung der Salden O_1, ..., O_n .
Die Frage ist: Wie können wir die minimale Menge an Übertragungen finden, die die optimale Verteilung erreichen? Können wir höchstens mit N-1 Transfers davonkommen?
Beispiel:
%Vor% Ja, Sie können immer mit nicht mehr als N-1 Transfer davonkommen. Hier ist ein Beweis durch Induktion:
N=2 ist es offensichtlich, dass nicht mehr als eine einzige Übertragung erforderlich ist. N>2 gibt es zwei Fälle:
i und j so dass B_i > O_i und B_j < O_j . Übertragen Sie min(B_i - O_i, O_j - B_j) von Konto i auf Konto j . Dadurch wird eines der beiden Konten ausgeglichen, wodurch das Problem auf den Fall N-1 reduziert wird.
Der Beweis ist konstruktiv und gibt Ihnen einen Algorithmus. Der Algorithmus versucht nicht, die Anzahl der Übertragungen zu minimieren.
Es ist einfach, Heuristiken zur Verringerung der Anzahl der Schritte zu erstellen. Es ist ein bisschen spät am Tag, dass ich über Optimalität nachdenke, aber es würde mich nicht überraschen, wenn sich das Problem als NP-schwer herausstellen würde.
Tags und Links algorithm