Programmieransatz finden

[groovecommander]

Hallo,

mein Problem ist vorerst kein reines PHP Problem, viel mehr ein programmiertechnisches.

Also,
ich habe eine Menge von 150 Einheiten. Daneben gibt es 5 verschieden Objekte (nicht die aus OOP...), mit jeweils unterschiedlichen Wertungen.
Bsp: A = 10, B = 20, C = 30, D = 40, E = 50
Insgesamt müssen 5 Objekte ausgewählt werden.

Nun sollen die Elemete so ausgewählt werden, dass die Summe der Objekte 150 ergibt.
Bsp. B,C,E,A,D = 150
oder D,D,D,A,B = 150
oder E,E,B,B,A = 150

Die Reihenfolge der Elemete spielt dabei keine Rolle. Es können auch Elemete wiederholt werden.

Hoffe es war halbwegs verständlich

Mir scheint das ist irgendein mathematische Optimierungsproblem. Nur kenn ich mich damit nicht so gut aus und würde mich über Anregungen freuen.

Mein erster Gedanke wäre eine Schleife folgendermaßen: 5xE auswählen (=250), prüfen ob 250 < 150 -> hier der Fall, letztes Element entfernen und dafür 4xE und 1xD (=240). Dann eben so weiter bis irgendwann 150 kommt.
Damit erhalte ich aber immer die gleichen Elemente. Ich möchte gern, dass die Elemente möglichst verschieden sind (s.o.).

Wer kann mir hier einen Lösungsansatz geben. Habe echt keine Idee mehr.

Vielen Dank und beste Grüße

[Flor1an]

Das hört sich für mich sehr nach einer Art Rucksackproblem – Wikipedia an. Da du aber Elemente mehrfach verwenden willst ist es etwas anders.

Das Problem ist, dass es sich nicht effizient lösen lässt, sondern mehr oder weniger nur per Brute-Force (alle Kombinationen ausprobieren). Heißt für wenige Elemente ist das noch möglich, bei sehr vielen hingegen wirst du zu keiner Lösung mehr kommen können.

[Asipak]

Was soll das denn werden, wenn es fertig ist? Hört sich nach Permutation an, bei der es noch eine Bedingung zu beachten gilt. Nur wozu soll das Ganze gut sein?

[edit]

Das hört sich für mich sehr nach einer Art Rucksackproblem an.

Wieder was gelernt!

[nikosch]

Hoffe es war halbwegs verständlich

Negativ. Oben zeigst Du doch bspw., dass es drei Lösungen gibt.

Nun sollen die Elemete so ausgewählt werden, dass die Summe der Objekte 150 ergibt.
Bsp. B,C,E,A,D = 150
oder D,D,D,A,B = 150
oder E,E,B,B,A = 150

Die Reihenfolge der Elemete spielt dabei keine Rolle. Es können auch Elemete wiederholt werden.

Und nun? Nach welchen Kriterien soll jetzt entschieden werden? Was, wenn es keine Kombination gibt? Oder geht es immer nur um die obigen Werte und immer nur um 150? Wie aufwendig darf die Berechnung sein? ...

[Sirke]

Das Problem ist glücklicherweise weniger das Rucksackproblem als das Lösen von zwei linearen Gleichungen mit n unbekannte Variablen. Seien kleine Buchstaben die Anzahl der Objekte und große Buchstaben die Bewertung/das Gewicht der Objekte, dann ergeben sich folgende Gleichungen:
N = a_0 * A_0 + a_1 * A_1 + ... + a_m * A_m
n = a_0 + a_1 + ... + a_m
mit m verschiedenen Objekten und der Gesamtwertung N bei einer Auswahl von n Objekten.

Für deinen Fall lässt sich das Gleichungssystem vereinfachen:
150 = a*A + b*B + c*C + d*D + e*E
5 = a + b + c + d + e

Ein solches Gleichungssystem ist lösbar in der Menge der reellen Zahlen, aber nicht zwingend in der Menge der ganzen Zahlen oder sogar nur der Menge der natürlichen Zahlen einschließlich der Null!

Soll nur irgendeine Lösung gefunden werden oder sollen alle Lösungen gefunden werden oder überhaupt geprüft werden ob eine Lösung existiert?

[groovecommander]

Das hört sich für mich sehr nach einer Art Rucksackproblem – Wikipedia an. Da du aber Elemente mehrfach verwenden willst ist es etwas anders.

Das Problem ist, dass es sich nicht effizient lösen lässt, sondern mehr oder weniger nur per Brute-Force (alle Kombinationen ausprobieren). Heißt für wenige Elemente ist das noch möglich, bei sehr vielen hingegen wirst du zu keiner Lösung mehr kommen können.

Das mit dem Rucksack - Problem ist mir bei der Recherche auch schon untergekommen. Doch ich glaube das passt nicht so richtig.
Der BruteForce-Gedanke wäre auch eine Idee. Alle Möglichkeiten ausprobieren, bei denen die Summe 150 ergibt. Rein mathematisch sollte es sich doch dabei um eine Kombination mit Wiederholung handeln, oder? Falls das so ist und ich mich nicht verrechnet habe, dann sollten 756 Möglichkeiten überprüft werden. Sollte eigentlich machbar sein...
Aber vielleicht gibt es ja noch einen eleganteren Weg?

Und nun? Nach welchen Kriterien soll jetzt entschieden werden?

Die Entscheidung soll der User treffen. Ich möchte ihm nur z.B. 3 Kombinationsmöglichkeiten anbieten.

Was, wenn es keine Kombination gibt?Oder geht es immer nur um die obigen Werte und immer nur um 150?

Da es so ist wie oben beschrieben, gibt es immer eine/mehrere Lösung(en)

Wie aufwendig darf die Berechnung sein? ...

So gering wie möglich.

Soll nur irgendeine Lösung gefunden werden oder sollen alle Lösungen gefunden werden oder überhaupt geprüft werden ob eine Lösung existiert?

Besser wäre wenn alle Lösungen gefunden werden, sodass der User selbst entscheiden kann welche ihm am besten passt. Wenn es zuviele sind, dann eben nur eine zufällige Auswahl.

Vielen Dank für Eure Hilfe

[nikosch]

dann eben nur eine zufällige Auswahl.

Schon wieder so eine präzise Aussage

Also wenn es um eine feste Menge geht, würde ich einmalig - meinetwegen Bruteforce - alle Kombinationen ermitteln und dann irgendwo hinterlegen. Ansonsten ist es natürlich das Rucksackproblem, nur mit der speziellen Einschränkung, dass der Wert genau erreicht werden muss.

[Sirke]

Es ist immernoch kein richtiges Rucksackproblem, weil es kein NP-vollständiges Problem ist.

Ich würde wenn alle Lösungen gesucht werden wirklich alle Kombinationen durchprobieren und die Schleifen anhand der Unterbedingung (Auswahl von festen n Objekten) abbrechen lassen. Evtl kann man vorher die maximale Anzahl jedes Objektes bzw in den Schleifen die zu dem Zeitpunkt noch maximale Anzahl des folgenden Objektes berechnen.

Alle Kombinationen bei einer Auswahl von n Objekten aus einer Menge mit m verschiedenen Objekten lassen sich mit m^n berechnen, wobei sich diese Schranke sehr schnell nach unten verschiebt (s.o.)!