Ist das Problem NP-schwer?

Question

Ich versuche, mit einem vernünftigen Algorithmus für dieses Problem zu finden:

Angenommen, Sie haben eine Reihe von Bällen. Jede Kugel hat mindestens eine Farbe, sondern auch mehrfarbig sein kann. Jede Kugel hat auch eine Nummer. Darüber hinaus gibt es eine Reihe von Boxen, die jeweils nur eine Farbe sind. Das Ziel ist es, die Summe der Zahlen auf den Kugeln in den Boxen zu maximieren, und die einzigen Regeln sind:

• , um eine Kugel in einem Feld, um es zu platzieren zumindest hat die Farbe der Box haben auf sie
• Sie können nur in jeder schiebt den Ball lässig Box.

Zum Beispiel können Sie einen blauen und grünen Ball in ein blaues Feld oder in einem grünes Feld, aber nicht in ein rotes Feld.

Ich habe mit ein paar Optimierungen, die helfen, eine Menge in Bezug auf die Laufzeit kommen. Zum Beispiel können Sie die Kugeln in absteigender Reihenfolge des Punktwertes sortiert werden. Dann, wie Sie von den höchsten Zahl zum niedrigsten gehen, wenn nur der Ball eine Farbe hat, und es gibt keine andere höheren Punkt Kugeln, die die Farbe enthalten, können Sie es in diesem Feld setzen (und damit, dass das Feld entfernen und diesen Ball aus dem übrige Kombinationen).

Ich bin nur neugierig ist, es gibt eine Art von dynamischem Algorithmus für diese Art von Problem, oder wenn es nur das Reiseproblem in der Verkleidung. Würde es helfen, wenn ich es höchstens X Farben kannten, waren? Jede Hilfe wird sehr geschätzt. Dank!

---

Bearbeiten - hier ist ein einfaches Beispiel:

Ball:

• 1 rote Kugel - 5 Punkte
• 1 blaue Kugel - 3 Punkte
• 1 grün / rote Kugel - 2 Punkte
• 1 grün / blaue Kugel - 4 Punkte
• 1 rot / blaue Kugel - 1 Punkt

Boxen:

• 1 rot
• 1 blau
• 1 grün

Optimale Lösung:

• rote Kugel im roten Kasten
• blaue Kugel im blauen Kasten

• grün / blaue Kugel im grünen Kasten

  Gesamtwert: 12 Punkte (5 + 3 + 4)

Answer 1

Dies ist ein Spezialfall des Maximalgewicht Matching-Problem auf einem gewichteten zweiteiligen Graphen . Konstruieren ein Graphen, deren linken Ecken entsprechen Kugeln, des rechten Ecken entsprechen Kästen und mit der Kante einen Ball und eine Schachtel mit einem Gewicht V Füge wobei V die Nummer auf dem Ball, wenn der Ball in der Schachtel gelegt werden, und 0 sonst . Fügen Sie zusätzliche Boxen oder verbunden Bälle auf die andere Seite mit Kanten von Gewicht Null, bis Sie die gleiche Anzahl von Eckpunkten auf jeder Seite haben. Die Zuordnung Sie suchen durch den Satz von Kanten von Nicht-Null-Gewicht in der maximalen (gesamt) Gewichtsanpassung in der resultierenden Kurve bestimmt wird.

Der Zuweisungsalgorithmus kann in O (n ^ 3) Zeit gelöst werden, wobei n hier das Maximum der Anzahl von Kugeln oder Box, die ungarische Methode . (Übrigens, soll ich den Haftungsausschluss, dass ich nur den ungarischen Algorithmus erwähnen, weil es das theoretische Ergebnis ist ich zufällig mit vertraut sein und sie beantwortet vermutlich die Frage im Titel, ob das ursprüngliche Problem ist NP-hart. Ich habe keine Ahnung ob es der beste Algorithmus zur Verwendung in der Praxis.)

Answer 2

Haben Sie eine gierige alg versucht? Sortieren nach Punkten / Wert und in Feld, wenn möglich. Wenn es im, Ausnahmen ID fehlt wie sie sehen.