MySQL encontrando subtotais

Question

EDITAR:

Disseram -me que fazer vocês lerem significa que eu recebo menos atenção. Me desculpe. Aqui está uma versão mais simples:

Bill recebeu US $ 100 em itens de uma loja.

Ele quer devolver o suficiente dos itens para recuperar exatamente US $ 30 dólares.

A loja tem um sistema de ponto de retorno que o ajudará a fazer isso.

Aqui estão os dados depois que ele digitaliza seus itens:

       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

Provavelmente perdi algumas opções, já que inventei tudo isso.

Então, a grande questão é:

Existe uma maneira (com o grupo, provavelmente) ter uma consulta que retornaria uma combinação sempre possível de itens?

Obrigado!

uma

Answer 1

Se o número de itens forem pequenos o suficiente, você poderá forçar isso com o SQL. Pode ser uma solução rápida em escrever, mas você provavelmente deseja fazer algo mais inteligente. Parece o "Problema da mochila"O que é NP completo.

Se o número de itens for grande, você precisará se aprofundar em algoritmos de programação dinâmica. Você precisa se perguntar o quanto isso é importante para o seu aplicativo.

Se o número de itens for relativamente pequeno, você poderá forçar isso. Uma instrução SQL de força bruta (que é o que você pediu) que encontra combinações de 1,2 ou 3 itens que correspondem é o seguinte. Se isso não for satisfatório, talvez o SQL não seja a ferramenta certa para este trabalho.

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

No Oracle, você usaria a função Cube para transformar isso em uma versão genérica, sem ter certeza de um equivalente ao MySQL.

Answer 2

Você está pedindo todos os subconjuntos que resumem exatamente US $ 30.

Isso parece muito com o Problema da soma do subconjunto, e Problema da mochila, então duvido fortemente que você possa fazer isso com uma consulta simples. Você provavelmente teria que recorrer ao T-SQL, mas mesmo isso provavelmente pareceria feio.

Eu acho que a programação é o caminho a seguir aqui.

Answer 3

Eu não acho que o grupo por pode fazer isso.

Não consigo pensar em uma maneira melhor do que encontrar/tentar todas as permutações, seja na sua linguagem de programação de escolha ou com um procedimento armazenado.

Se você tivesse itens com mais de 30 $, poderá omitê -los.

Haveria algumas melhorias se você quisesse uma opção "melhor" por alguns critérios.

Answer 4

Esse problema é de fato p/np. Por exemplo, você provavelmente não consegue encontrar os preços dos artigos mais adequados, sem pesquisa de força bruta, e se sua loja de clientes é grande - você poderá encontrar essa pesquisa com duradoura.

Você pode usar alguns dos algoritmos existentes que podem dar um bom palpite, mas tenho medo de que sejam todos que não são SQL.

Eu sugeriria fazer a aproximação do seu problema:

Crie procedimento/consulta que encontre um artigo que melhor se encaixe no preço e que o chame novamente para uma nova alteração que você possui. Não é perfeito, mas fará o trabalho.