MySQL trouver des sous-totaux

Question

EDIT:

On me dit que vous faire les gars des moyens de lecture que je reçois moins d'attention. Mes excuses. Voici une version plus simple:

Bill a $ 100 dollars la valeur des articles d'un magasin.

Il veut revenir assez des articles pour obtenir exactement $ 30 dollars de retour.

Le magasin a un point de système de retour qui l'aidera à le faire.

Voici les données après qu'il scanne ses articles:

       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

J'ai probablement manqué quelques options, depuis que je fait tout cela.

Alors, la grande question est:

Y at-il un moyen (avec GROUP BY, sans doute) d'avoir une requête qui renverrait combinaison possible d'éléments jamais?

Merci!

Answer 1

Si le nombre d'éléments sont assez petits, vous pouvez la force brute avec ce SQL. Cela pourrait être une solution rapide à écrire, mais vous voulez sans doute faire quelque chose plus intelligent. On dirait que le " problème havresac" qui est NP complet.

Si le nombre d'éléments est grande, vous devez plonger dans les algorithmes de programmation dynamique. Vous devez vous demander comment cela est important pour votre application.

Si le nombre d'éléments est relativement faible, vous pourriez être en mesure de forcer cette-brutale. Une instruction SQL de la force brute (qui est ce que vous avez demandé) qui trouve des combinaisons de 1,2 ou 3 éléments qui correspondent est la suivante. Si ce n'est pas satisfaisante, alors peut-être SQL est pas le bon outil pour ce travail.

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

Dans Oracle, vous pouvez utiliser la fonction CUBE pour la transformer en une version générique, pas sûr équivalent MySQL.

Answer 2

Vous vous demandez tous les sous-ensembles qui somme jusqu'à exactement 30 $.

Cela semble un peu comme le problème sous-ensemble somme et

Je ne pense pas que le groupe peut le faire par.

Je ne peux pas penser à une meilleure façon de trouver / essayer toutes les permutations, que ce soit dans votre langage de programmation de choix ou d'une procédure stockée.

si vous aviez des items plus que 30 $, vous pouvez les omettre.

il y aurait des améliorations si vous vouliez une « meilleure » option par certains critères.

Ce problème est en fait P / NP. par exemple, vous pouvez probablement pas trouver les meilleurs prix de l'article de montage, sans recherche de force brute, et si vos clients magasin est grand - vous pouvez constater que la recherche très longue durée.

Vous pouvez utiliser certains des algorithmes existants qui peuvent vous donner assez bien deviner, mais je crains que ce sont tous les non-SQL.

Je suggère de faire approximation de votre problème:

Créer la procédure / requête qui trouve un article qui convient le mieux voul, et que l'appeler à nouveau pour le nouveau changement que vous avez. Pas parfait, mais fera le travail.

Answer 3

Answer 4

Answer 5

Je ne pense pas que le groupe peut le faire par.

Je ne peux pas penser à une meilleure façon de trouver / essayer toutes les permutations, que ce soit dans votre langage de programmation de choix ou d'une procédure stockée.

si vous aviez des items plus que 30 $, vous pouvez les omettre.

il y aurait des améliorations si vous vouliez une « meilleure » option par certains critères.

Answer 6

Ce problème est en fait P / NP. par exemple, vous pouvez probablement pas trouver les meilleurs prix de l'article de montage, sans recherche de force brute, et si vos clients magasin est grand - vous pouvez constater que la recherche très longue durée.

Vous pouvez utiliser certains des algorithmes existants qui peuvent vous donner assez bien deviner, mais je crains que ce sont tous les non-SQL.

Je suggère de faire approximation de votre problème:

Créer la procédure / requête qui trouve un article qui convient le mieux voul, et que l'appeler à nouveau pour le nouveau changement que vous avez. Pas parfait, mais fera le travail.

Answer 7

Ce problème est en fait P / NP. par exemple, vous pouvez probablement pas trouver les meilleurs prix de l'article de montage, sans recherche de force brute, et si vos clients magasin est grand - vous pouvez constater que la recherche très longue durée.

Vous pouvez utiliser certains des algorithmes existants qui peuvent vous donner assez bien deviner, mais je crains que ce sont tous les non-SQL.

Je suggère de faire approximation de votre problème:

Créer la procédure / requête qui trouve un article qui convient le mieux voul, et que l'appeler à nouveau pour le nouveau changement que vous avez. Pas parfait, mais fera le travail.

Answer 8

Answer 9