MySQL Finden von Subtotalen

Question

BEARBEITEN:

Mir wurde gesagt, dass ich euch lesen soll, dass ich weniger Aufmerksamkeit bekomme. Entschuldigen Sie. Hier ist eine einfachere Version:

Bill erhielt Artikel im Wert von 100 Dollar aus einem Geschäft.

Er möchte genug von den Artikeln zurückgeben, um genau 30 Dollar zurückzubekommen.

Der Laden hat einen Rückgabesystem, der ihm hilft.

Hier sind die Daten, nachdem er seine Artikel gescannt hat:

       item ¦   price ¦

socks             4.00
cheap tv         22.00
book on tape      9.00
book on paper     7.00
party hats        3.00
picture frame    10.00
hammer            5.00
juicer           16.00
mysql guide      24.00

total items  ¦ total price ¦
            9   100.00

Option 1
===============
item ¦          price ¦
cheap tv        22.00
party hats       3.00
hammer           5.00
===============

Option 2
===============
item ¦          price ¦

socks            4.00
picture frame   10.00
juicer          16.00
===============

Option 3
===============
item ¦          price ¦

book on tape    9.00
hammer          5.00
juicer         16.00

Ich habe wahrscheinlich ein paar Optionen verpasst, da ich all das erfunden habe.

Die große Frage ist also:

Gibt es einen Weg (mit Gruppe von, wahrscheinlich), eine Abfrage zu haben, die jemals eine mögliche Kombination von Gegenständen zurückgeben würde?

Vielen Dank!

a

Answer 1

Wenn die Anzahl der Elemente klein genug ist, können Sie dies mit SQL erzwingen. Dies mag eine schnelle Schreiblösung sein, aber Sie möchten wahrscheinlich etwas klügeres tun. Klingt nach dem "Rucksackproblem"Welches ist NP vollständig.

Wenn die Anzahl der Elemente groß ist, müssen Sie sich mit dynamischen Programmieralgorithmen befassen. Sie müssen sich fragen, wie wichtig dies für Ihre Bewerbung ist.

Wenn die Anzahl der Artikel relativ gering ist, können Sie dies möglicherweise brutal machen. Eine Brute-Force-SQL-Anweisung (die Sie gefragt haben), die Kombinationen von 1,2 oder 3 Elementen findet, die übereinstimmen, ist wie folgt. Wenn dies nicht zufriedenstellend ist, ist SQL möglicherweise nicht das richtige Werkzeug für diesen Job.

SELECT
   i1.id AS id1,
   NULL AS id2,
   NULL AS id3,
   i1.amount
FROM
   items i1
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount AS total
FROM
   items i1,
   items i2
WHERE
   i1.amount + i2.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id
UNION ALL
SELECT
   i1.id AS id1,
   i2.id AS id2,
   i3.id AS id3,
   i1.amount + i2.amount + i3.amount AS total
FROM
   items i1,
   items i2,
   items i3
WHERE
   i1.amount + i2.amount + i3.amount = 30 AND
   i1.id <> i2.id AND
   i1.id <> i3.id AND
   i2.id <> i3.id

In Oracle würden Sie die Cube -Funktion verwenden, um diese in eine generische Version zu verwandeln, nicht sicher über ein MySQL -Äquivalent.

Answer 2

Sie fragen nach allen Teilmengen, die genau 30 US -Dollar betragen.

Das klingt sehr nach dem Summenproblem, und Rucksackproblem, Ich bezweifle sehr, dass Sie dies mit einer einfachen Frage tun können. Sie müssten sich wahrscheinlich an T-SQL wenden, aber selbst das würde wahrscheinlich hässlich aussehen.

Ich denke, das Programmieren ist der richtige Weg hierher.

Answer 3

Ich glaube nicht, dass Gruppe von es kann.

Ich kann mir keinen besseren Weg vorstellen, als alle Permutationen zu finden/auszuprobieren, entweder in Ihrer Programmiersprache der Wahl oder mit einem gespeicherten Verfahren.

Wenn Sie Artikel über 30 $ hätten, könnten Sie sie weglassen.

Es würde einige Verbesserungen geben, wenn Sie nach einigen Kriterien eine "beste" Option wünschen.

Answer 4

Dieses Problem ist in der Tat P/NP. Zum Beispiel können Sie wahrscheinlich nicht die am besten geeigneten Artikelpreise finden, ohne die Suche nach Brute Force, und wenn Ihr Kunden in großer Bedeutung ist, können Sie diese Suche sehr langlebig finden.

Sie können einige der vorhandenen Algorithmen verwenden, die Ihnen ziemlich gute Vermutungen geben können, aber ich befürchte, dass sie alle nicht-SQL sind.

Ich würde vorschlagen, Ihr Problem zu nähern:

Erstellen Sie eine Prozedur/Abfrage, die einen Artikel findet, der am besten geeignet ist, und rufen Sie ihn noch einmal für neue Änderungen an. Nicht perfekt, wird aber den Job machen.