die Suche nach einem sauberen, effizienten Weg, um eine Reihe von Daten gegen bekannte Muster

Question

Mit php5.2 und MySQL 4.1.22

ich auf etwas, das auf dem ersten, einfache schien gekommen zu passen, aber da habe mich ausgewichen in Bezug auf eine einfache, saubere Lösung.

Wir haben vordefinierte „Pakete“ von Produkt. Paket 1 kann die Produkte A, B und C enthalten. Paket 2 kann A, C, D und G enthalten usw. Die Pakete haben eine Größe von 3 bis 5 Produkten.

Nun kann ein Kunde alle 10 Produkte auswählen und ein „custom“ Paket machen. Da wir bereits bestimmte vordefinierte Pakete haben, möchten wir, wenn möglich, das benutzerdefinierte Paket mit kleineren vorhandenen Paketen (für die Versandfreundlichkeit) erstellen.

So wählt zum Beispiel ein Kunde ein 'benutzerdefiniertes Paket' der Produkte A, B, C, D, E und F. Wir haben bereits ein vordefiniertes Paket, das A, B und C namens Foo enthält. So würde der Auftrag dann Foo, D, E und F. seiner

Der Haken ist, die geringste Menge an einzelnen Positionen haben, durch die geringste Menge an Paketen gefolgt. Zum Beispiel:

benutzerdefiniertes Paket: A, B, C, D, E, F, G, H, I, J.

Predefined Verpackung (1): A, B, C, D, E

Predefined Package (2): A, B, C

Predefined Verpackung (3): D, E, F

Wenn ich einfach um die größte Übereinstimmung nehmen, dann ich habe 1 (5pc) Paket und 5 Einzelstücke. Weder Package (2) noch (3) können mit den verbleibenden Items erstellt werden.

Wenn ich tiefer schauen, finde ich, dass von Paketen nicht inbegriffen ist (1) I statt Paket bauen (2) und Verpackung (3). Was bedeutet, ich habe 2 Pakete und 4 einzelne Artikel (eine bessere Wahl in dieser Geschäftsregel).

Wie ich MySQL bin mit, ich bin unter der Zurückhaltung der nur eine Schicht von Unter wählen zur Verfügung zu haben (meines Wissens). Also muss diese Art in PHP ausgeführt werden. Ich habe mit array_intersect() betrachtet, um Übereinstimmungen zu ermitteln, aber jede gefundene Methode wächst exponentiell in Bezug auf die Verarbeitung, da die Anzahl der vordefinierten Pakete linear wächst.

Ich lief dies durch ein paar andere Coder Freunde und wieder, während es wie es schien eine einfache Antwort sein sollten wir alle, dass es nicht so einfach war gefunden, wie es scheint. Also dachte ich, ich würde es hier als nette Noodle Bahre posten. Vielen Dank im Voraus für Ihre Zeit!

Answer 1

Das Problem ist im allgemeinen eine „harte“ ein (hinsichtlich der Rechenkomplexität gesprochen). Tatsächlich klingelt es in meinem Hinterkopf, dass es sich wahrscheinlich auf eines dieser klassischen Algorithmusprobleme wie das Knapsack problem reduziert, aber ich kann ihm keinen richtigen Namen geben.

jedoch mit einem so kleinen Problem Raum (sie nur 10 Produkte auswählen können), sollte es ziemlich schnell sein, nur das, was Brute-Force. Wenn jemand einen benutzerdefinierten Build einreicht, greift er ihn rekursiv mit allen Möglichkeiten an und sieht, welcher der beste ist.

Das heißt, nehmen Sie die Komponenten, die sie ausgewählt haben, und versuchen Sie zuerst, die Komponenten von "Paket 1" daraus zu entfernen. Wenn das möglich ist, nimm die restlichen Komponenten und versuche, die Komponenten von "Package 2" daraus zu nehmen, etc. Behalte die beste Lösung im Auge, die du bisher gefunden hast.

Wenn es immer noch nicht schnell genug ist (aber ich denke es wird wahrscheinlich, je nachdem wie viele vorgefertigte Pakete Sie haben), könnten Sie einige dynamic programming Methoden anwenden, um es zu beschleunigen.

---

Edited hinzufügen:

Je nach Anzahl der Möglichkeiten und wie lange dies dauert tatsächlich zu laufen, sollten Sie den Code schreiben, die ich oben beschrieben, und dann gehen Sie einfach weiter und Pre Berechnen Sie alle Lösungen für jede mögliche Kombination. Wenn jemand einen benutzerdefinierten Build einreicht, müssen Sie die Antwort nur abrufen, anstatt sie jedes Mal von Grund auf neu zu berechnen.

Auch wenn Sie sie nicht alle vorberechnen möchten, empfehle ich, das Ergebnis jedes Mal zu speichern, wenn jemand eine benutzerdefinierte Build erstellt, und in der Zukunft, wenn jemand anders die gleichen benutzerdefinierten Builds erstellt um die Lösung neu zu berechnen.

Answer 2

Ich schlage vor, Sie die Kunden helfen lassen. Zeigen Sie in den Produktauswahlbildschirmen, welche Packungssätze verfügbar sind, und lassen Sie sie die Kombinationen erstellen (mit angemessenen Preisen, so dass die Summe der Onesies ausreicht, um die spezielle Handhabung abzudecken).

Answer 3

Entschuldigung, dass Sie Ihr Problem ein wenig komplizierter machen. :-)

Sie möchten vielleicht bereits mögliche Lösungen vorberechnen, oder lassen Sie die Kunden tatsächlich aus den vordefinierten Paketen selbst wählen: Was passiert, wenn ein vordefiniertes Paket nicht mehr vorrätig ist?

Was ist, wenn keine Lösung existiert, um die Bestellung zu diesem Zeitpunkt abzuschließen? Würden Sie dann einen Teil der Bestellung versenden, und wenn ja: Würden Sie einzelne Artikel einschließen, selbst wenn Sie wissen, dass Sie zu einem späteren Zeitpunkt ein vordefiniertes Paket auswählen könnten?

Und sind Sie wirklich sicher, dass vordefinierte Pakete keine "Präferenz" zugewiesen bekommen? Wie ist das vordefinierte Paket bei der Bestellung von "ABCD" und vordefinierten Paketen "ABC" und "BCD" auszuwählen? Wenn Sie zum Beispiel wissen, dass das vordefinierte Paket "ABC" oft nicht auf Lager ist, dann wird vielleicht "BCD" bevorzugt, wann immer es möglich ist.

Also: vielleicht müssen Sie einige Modellierung verwenden, in denen Sie leicht einige hart-codierte Regeln ändern können, anstatt zu versuchen, eine automatisierte Lösung zu finden. Dies könnte natürlich PHP selbst sein.