Zuteilungsproblem NP-Vollständig?

Guten Abend,

kann mir jemand bitte kurz bei der Aufgabe helfen:

"Jedes der m Bewohner in Oestrich-Winkel hat seinen Wunschzettel für das Christkind geschrieben und verschiedene Geschenkwünsche aus einem Katalog mit n verschiedenen Geschenken aufgeschrieben. Ein Bewohner wird glücklich an Heiligabend, wenn er mindestens einen seiner Wünsche erfüllt bekommt. Jeder der k Weihnachtsengel kann sich auf genau ein Geschenk aus dem Katalog spezialisieren und eine beliebig große Stückzahl davon herstellen. Allerdings sind die Engel nicht in der Lage, an verschiedenen Geschenken zu arbeiten. Wenn sie sich einmal spezialisiert haben,können sie in dieser Weihnachtssaison nur diesen Geschenktyp herstellen.

Die Problemstellung für das Weihnachtsgeschenkeproduktionsproblem ist also, ob es zu einem gegebenen Katalog mit n Geschenken eine Auswahl von k Geschenken gibt, sodass jeder Bewohner glücklich wird.

a) Gegeben sei der folgende Weihnachtskatalog: {Schlittschuhe, Eisenbahn, Counterstrike, Smartphone, Fußball, Butterfly-Messer, Puppenhaus, Schlagring}.

Angenommen, es gibt 3 Engel, können damit die folgenden Bewohner mit ihren jeweiligen Wunschzetteln glücklich gemacht werden?

Andrea: {Schlittschuhe, Fußball}

Ben: {Eisenbahn, Butterfly-Messer, Puppenhaus}

Chantal: {Smartphone, Counterstrike, Buch}

Diana: {Fußball, Puppenhaus, Smartphone}

Eve: {Counterstrike, Schlagring}

Fabienne: {Eisenbahn, Butterfly-Messer}

Georg: {Schlagring, Counterstrike, Puppenhaus}

Heidi: {Eisenbahn, Fußball, Schlittschuhe}

Wenn ja, geben Sie eine mögliche Zuordnung der Engel zu den Geschenken an, wenn nein,begründen Sie, warum es nicht geht.

b) Zeigen Sie, dass dasWeihnachtsgeschenkeproduktionsproblem NP-vollständig ist"

-----------------------

Ich verstehe nicht ganz, warum die Zuordnung ein Problem darstellt. Wenn Engel A einfach die Schlittschuhe, die Eisenbahn und Counterstrike produziert; und Engel B das Smartphone, den Fußball und das Butterfly-Messer und C die Puppe und den Schlagring, dann kommt sich doch niemand in die Quere? Die Sachen müssen ja nicht zeitgleich produziert werden, oder? Ganz so einfach kann es aber nicht sein. Soll ich hier mit Bipartiness, Färbungsproblem argumentieren? Ich denke, da in b) steht, dass das Problem NP-vollständig ist, dass es deswegen keine Lösung für a) geben wird. Aber ich verstehe nicht ganz, wie man hier vorgehen soll.

Computer, Studium, Mathe, rechnen, Datenstrukturen, Effizienz, Färbung, Informatik, Modellierung, np, Uni, Algorithmus, Komplexität, Algorithmen und Datenstrukturen, P.
1 Antwort

Meistgelesene Fragen zum Thema P.