[DSAL] Gegenstände, die mitgenommen werden

[fortuneNext]

Hi,

ihr kennt ja diese Aufgabe, dass eine gewisse Anzahl von Gegenständen gewisse Preise haben und Leute diese mieten wollen, und nun die Frage ist, wen man mitnimmt. Das soll sich ja mit Flussnetzwerken lösen lassen, leider kann ich nirgens finden, wie genau das geht? Kann das jemand erklären?

Zusatz: Genauso ist es in der erweiterten Form, sprich dem Aufgabentyp, der in der Klausur dran kam: Gegenstände können gekauft oder gemietet werden. Wie funkioniert das?

Gruß
Tim

[Someguy]

Die (fast?) gleiche Aufgabe gabs doch auf einem der Übungsblätter. Diese gibt es mit Lösung auf der offiziellen DSAL Seite hier

[mugen]

Ich weiß nicht genau was in der Vorlesung die du gehört hast dran kam, ich versuchs aber trotzdem mal.

Als erste musst du das Flussnetzwerk modellieren, dazu brauchst du in der Menge A die Knoten die die Personen repräsentiert und die Menge B die die Gegenstände repräsentiert.

Kanten gibt es von x aus A nach y aus B wenn Person x Gegenstand y mieten will, mit Kantenkosten c(y)

Dann füge noch quelle [senke] hinzu und verbinde sie mit allen knoten aus A [B]
Gehe ich recht in der Annahme dass jeder Gegenstand nur 1x ausgeliehen werden darf und jede Person nur einen nehmen darf? Dann sind alle Kantenkapazitäten 1.


Lösen kannst du das dann mittels des Cycle-canceling Algorithmus oder was ihr auch immer für einen Algo in der Vorlesung hattet.