Kombinatorik-Problem: Optimierte Auswahl von Zutaten

[blackfin]

Hallo liebe Foren-Profis,

Ich habe ein kombinatorisches Problem, über das ich schon den ganzen Tag grüble, allerdings glaube ich langsam, ich hab da einen Knoten im Kopf und komme nicht auf einen Lösungsansatz.

Folgende Problemstellung ist gegeben:

- Vorhanden sind 2000 Rezepte mit diversen Zutaten.
- Zutaten gibt es insgesamt 100 Stück.
- Es dürfen aber nur 20 Zutaten eingekauft werden.
Frage: Welche 20 Zutaten müssen gekauft werden, um möglichst viele der 2000 Rezepte abzudecken.

Irgendwie habe ich einen Drehwurm im Kopf :(
Kann mit jemand vielleicht einen Lösungsansatz oder Hilfestellung geben?

P.S. Das ist KEINE Schul-Mathematik-Aufgabe, sondern ein reelles Problem, mit dem ich mich da rumschlagen muss :)

[jfheins]

Viel Spaß beim alle-Möglichkeiten-durchprobieren - ich vermute mal, das problem ist np-vollständig ;)

Das Problem erinnert an das Rucksack-Problem, welches np-vollst. ist: http://de.wikipedia.org/wiki/Rucksackproblem

Mit anderen Worten: Wenn meine Vermuting stimmt, kannst du Heuristiken entwickeln, die eine gute Lösung liefern - um jedoch die beste Lösung zu finden musst du alles durchprobieren.

[Mithrandir]

Was doch aber bei den heutigen Rechenleistungen kein Problem darstellt, oder?

[ToFaceTeKilla]

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

[Satty67]

Ist ja nur eine Logik-Frage, da wäre das auch als Schulaufgabe kein Problem.

Erste Idee von mir war, alle 2000 Rezepte durchgehen und für die darin enthaltenen Zutaten einen Zähler bei den Zutaten hoch zählen. Dann wären die meist gebrauchten Zutaten sichtbar. Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

[blackfin]

Zitat:

Zitat von ToFaceTeKilla

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

Möglichst viele vollständig. Sonst ist das Rezept ja nicht mischbar, wenn eine Zutat dazu fehlt. :)

Ja, das Rucksack-Problem habe ich mir auch angeschaut, aber irgendwie hat es meinem Kopf auhc nicht geholfen, einen Lösungs-Ansatz zu finden ;/

Danke aber schon einmal für die bis jetzt stehenden Antworten!

[himitsu]

Praktisch alle möglichen Kombinationen an Zutaten durchgehen und für jede Möglichkeit die Anzahl der Rezepte bestimmen, welche damit möglich wären.

[Mithrandir]

Zitat:

Zitat von Satty67

Aber kann ja sein das es nicht automatisch die Zutaten sind, mit denen auch die meisten Rezepte komplettiert sind?

Und wenn man ne Liste mit den 20 häufigsten Zutaten erstellt, und dann alle Rezepte auflistet, in denen nur Zutaten aus dieser Kategorie auftauchen? Dann müssten das doch imho die gesuchen sein, oder?

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier... :stupid:

[blackfin]

Zitat:

Zitat von Daniel G

@blackfin: Wenn das wirklich ein reales Problem ist: Wer braucht denn sowas, wenn ich mal fragen darf? Nur aus Neugier... :stupid:

Klar darfst du fragen!
Allerdings darf ich da wohl auch nicht zuviel sagen :(
Aber soviel: Es geht um Mischroboter und deren optimale Bestückung :)

[jfheins]

Zitat:

Zitat von Daniel G

Was doch aber bei den heutigen Rechenleistungen kein Problem darstellt, oder?

Vielleicht waren die zahlen nur nett gewählt um das Problem für das Forum zu vereinfachen ;)
Außerdem: Wenn es wirklich 100 Zutaten sind, ergibt das 5,36*10^20 Möglichkeiten.
Falls er einen 3GHz-Quanten-Quadcore hat und damit in jedem Takt 4 Möglichkeiten prüft braucht er immernoch 1,4 Jahre
(Natürlich nur, wenn das Problem wirklich NP-schwer ist ...)

Zitat:

Zitat von ToFaceTeKilla

Musst du möglichst viele Rezepte abdecken oder möglichst viele vollständig, also dass alle Zutaten vorhanden sind?

Was kann man mit einem Rezept machen, wenn man nicht alle Zutaten davon hat? :stupid: