Gibt es einen Algorithmus, der die beschränkte Eingabe an die mögliche Ausgabe anpasst?

Question

Ich arbeite an einem Problem, bei dem ein Benutzer eine Liste von Eingabeprodukten bereitstellt, die in verschiedene Endprodukte umgewandelt werden können. Jedes Eingangsprodukt hat einen bestimmten Satz von Ausgängen, die es werden könnte. Der Benutzer liefert auch eine Liste der erwarteten Ausgabeprodukte und wie viel von ihnen jeweils gewünscht wird. Ich schaue, ob es einen bekannten Algorithmus gibt, um die verschiedenen Eingaben an die Ausgaben anzupassen, um den Bedarf so gut wie möglich zu erfüllen.

Beispiel:

Produkt A können Produkte X und Y
Produkt B werden Produkte Y und Z werden können

Es sind 5 A und 7 B.
Können Sie 3 X machen, 4 Y und 6 Z?

Ich würde einen Ansatz mag, die mir die Ausgabe finden helfen würde:

3 A -> X
2 A -> Y
2 B -> Y
5 B -> Z
fehlt 1 Z

Answer 1

Sie dieses Problem, indem eine der max flow algorithms auf ein Flussnetz lösen kann wie folgt aufgebaut:

• Quellknoten S hinzufügen und Knoten T sink
• Für jeden Eingang Produkt hinzuzufügen Knoten A _i
• Für jedes Ausgangsprodukt hinzufügen Knoten Z _j
• Für jeden Eingang Produkt eine Kante von S hinzufügen, mit Kapazität gleich die Anzahl des entsprechenden Produkts
• Für jedes Ausgangsprodukt eine Kante mit einer Kapazität gleich die gewünschten Anzahl von dem entsprechenden Produkt von T
• von jedem A _{ihinzufügenund Z j füge eine Kante mit einer Kapazität gleich der Anzahl von A i Produkt}

Hier ist, wie das Netzwerk für Ihr Beispiel aussehen würde.

Wenn der max Strom zu der Gesamtkapazität der Eingabe T gleich ist, wird eine Lösung, die durch min cat definiert sind; Andernfalls ist eine Lösung nicht möglich.

Hinweis: Wenn alles, was Sie brauchen, ist ein Ja/Nein-Antwort ist, könnten Sie eine _i Knoten, beseitigen und Kanten von S an alle für diesen Ausgang gleich der Gesamt Z _j mit Kapazitäten hinzufügen, über Eingangsprodukte (dh X = 5, Y = 12 und Z = 7). Dies würde zu dem gleichen Entscheidungsergebnis führen, aber Sie wären nicht in der Lage herauszufinden, wie viele Eingabeprodukte jeder Art in dem Prozess verbraucht werden müssen.