MySQL búsqueda de subtotales

Question

EDIT:

Me han dicho que lo que ustedes leen medios consigo menos atención. Mis disculpas. Aquí hay una versión más simple:

Bill consiguió $ 100 dólares valor de los elementos de una tienda.

Él quiere volver lo suficiente de los elementos para obtener exactamente $ 30 dólares de vuelta.

La tienda cuenta con un sistema de punto de retorno que le ayudará a hacer esto.

Estos son los datos después de que escanea sus elementos:

       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

Probablemente perdí un par de opciones, desde que hice todo esto para arriba.

Por lo tanto, la gran pregunta es:

¿Hay alguna manera (con GROUP BY, probablemente) tener una consulta que devolvería siempre que sea posible combinación de elementos?

Gracias!

a

Answer 1

Si el número de elementos son lo suficientemente pequeño que puede fuerza bruta esto con SQL. Esto podría ser una rápida solución a escribir, pero es probable que desee hacer algo más inteligente. Suena como el " mochila problema ", que es NP completo.

Si el número de elementos es grande, tendrá que profundizar en algoritmos de programación dinámica. Usted tiene que preguntarse lo importante que es para su aplicación.

Si el número de elementos es relativamente pequeño, es posible que pueda ataque de fuerza bruta esto. Una declaración de fuerza bruta de SQL (que es lo que usted pidió) que encuentra combinaciones de 1,2 o 3 elementos que coinciden es la siguiente. Si esto no es satisfactorio, entonces tal SQL no es la herramienta adecuada para este trabajo.

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

En Oracle, debe utilizar la función CUBO de convertir esto en una versión genérica, no está seguro acerca de un equivalente de MySQL.

Answer 2

Usted está pidiendo todos los subconjuntos, que suman exactamente $ 30.

Esto se parece mucho a la subconjunto suma problema , y problema de la mochila , así que dudo fuertemente que puede hacer esto con una simple consulta. Probablemente usted tiene que dar vuelta a T-SQL, pero ni siquiera eso, probablemente se vería feo.

Creo que la programación es el camino a seguir aquí.

Answer 3

no creo por grupo puede hacerlo.

No puedo pensar en una manera mejor que encontrar / tratando todas las permutaciones, ya sea en su lenguaje de programación de elección o con un procedimiento almacenado.

si tuviera artículos de más de 30 $ se podría omitir ellos.

habría algunas mejoras si quería una "mejor" opción por parte de algunos criterios.

Answer 4

Este problema es, de hecho, P / NP. por ejemplo, es probable que no se puede encontrar el precio mejor artículo de ajuste, sin búsqueda de fuerza bruta, y si su tienda de clientes es grande - usted puede encontrar esa búsqueda muy larga duración.

Puede utilizar algunos de los algoritmos existentes que pueden darle conjetura bastante buena, pero me temo que son todos los no-SQL.

Yo sugeriría que ver aproximación de su problema:

Crea procedimiento / consulta que encuentra un artículo que mejor se adapte compro, y que la llaman otra vez el nuevo cambio que tener. No es perfecto, pero hará el trabajo.