Verteilung der Ressourcen von Anbietern bis zur maximalen Anzahl von Empfängern

Question

Betrachten Sie, dass es eine Stadt mit $ N $ Einwohner gibt, die Internet brauchen, und es gibt $ M $ Internetanbieter in der Stadt.Hier in der Stadt braucht jeder Wohnsitz Internet, und jeder Wohnsitz weiß, was ihm für den Anbieter zur Verfügung stehen.Ohne Resident $ I $ hat Liste der Anbieter $ a_i $ .Jeder Anbieter hat auch eine maximale Anzahl von Verbindungen, die er geben kann, dh Provider $ I $ kann bei Max $ k_i haben$ Verbindungen.Finden Sie die optimale Möglichkeit, das Internet bereitzustellen, damit die Anzahl der Bewohner mit Internet maximal ist.

Meine Gedanken zu der Frage ist, dass diese Frage wie ein Derivat des KNACK-Pack-Problems mit Einschränkungen aussieht, was die dynamische Programmierung vorschlägt, aber ich kann die Staaten nicht finden.Könnte mir jemand helfen?

Answer 1

Dieses Problem ist ein Fall von Maximales Flow-Problem .

Angenommen, wir erhalten Internetanbieter $ P_1, P_2, \ CDs, P_M $ und Bewohner $ r_1, r_2, \ CDs, R_N $ . Betrachten Sie ein nachfolgend angegebenes Durchflussnetzwerk.

.
• Knoten sind $ S, \ P_1, P_2, \ CDs, P_M, \ R_1, R_2, \ CDs, R_N, \ t $ , wobei $ s $ und $ T $ sind zwei zusätzliche Knoten, die für die Quelle und die Waschbecken stehen.
• Es gibt eine Kante zwischen $ s $ und jeweils $ p_i $ mit Kapazität $ k_i $ .
• Es gibt eine Kante zwischen $ p_i $ und $ r_j $ mit Kapazität 1, wenn $ p_i $ Kann Internet an $ r_j $ bereitstellen.
• Es gibt eine Kante zwischen jedem $ r_j $ und $ t $ mit Kapazität 1.

was wir wollen, ist, den maximalen Fluss von $ s $ bis $ t $ zu finden. < / p>

Es gibt Viele Algorithmen , um ein maximales Flussproblem bei der Polynomzeit zu lösen. Beispielsweise ford-fulkersonalgorithmus und Dinasalgorithmus ist ziemlich beliebt. Quellcode, der diese Algorithmen in verschiedenen Programmiersprachen implementiert, können problemlos gefunden werden.

all diesen Algorithmus erzeugt einen integralen maximalen Fluss, sodass wir uns keine Sorgen machen, wenn der berechnete maximale Durchfluss vorsieht, dass ein Anbieter 0,42 oder $ \ frac {sqrt2} 2 anbieten sollte $ Internet an einigen Bewohner. Sie können der Integral Flow theorem .