MySQL найти промежуточные итоги

Question

EDIT:

Мне сказали, что если вы, ребята, читаете, мне нужно меньше внимания. Мои извенения. Вот более простая версия:

Билл получил вещи в магазине на 100 долларов.

Он хочет вернуть достаточно вещей, чтобы получить ровно 30 долларов.

В магазине есть система Point of Return, которая поможет ему сделать это.

Вот данные после того, как он сканирует свои предметы:

       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

Я, вероятно, пропустил несколько вариантов, так как все это придумал.

Итак, большой вопрос:

Есть ли способ (возможно, с GROUP BY) иметь один запрос, который бы возвращал когда-либо возможную комбинацию элементов?

Спасибо!

а

Answer 1

Вы запрашиваете все подмножества, которые в сумме составляют ровно 30 долларов.

Это очень похоже на проблему суммы подмножеств и проблему ранца , поэтому я сильно сомневаюсь, что вы можете сделать это простым запросом. Возможно, вам придется обратиться к T-SQL, но даже это, вероятно, будет выглядеть уродливо.

Я думаю, что программирование - это путь сюда.

Answer 2

Если количество элементов достаточно мало, вы можете перебором с помощью SQL. Это может быть быстрое решение, но вы, вероятно, хотите сделать что-то умнее. Звучит как " проблема с рюкзаком ", которая завершена NP.

Если количество элементов велико, вам нужно углубиться в алгоритмы динамического программирования. Вы должны спросить себя, насколько это важно для вашего заявления.

Если количество предметов относительно невелико, вы можете сделать это. SQL-оператор грубой силы (то, что вы просили), который находит комбинации из 1,2 или 3 элементов, которые соответствуют, выглядит следующим образом. Если это неудовлетворительно, возможно, SQL не является подходящим инструментом для этой работы.

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

В Oracle вы использовали бы функцию CUBE, чтобы превратить ее в универсальную версию, не уверенную в эквиваленте MySQL.

Answer 3

Эта проблема на самом деле P / NP. Например, вы, вероятно, не сможете найти ЛУЧШИЕ подходящие цены на товары без поиска методом грубой силы, и, если у ваших клиентов большой магазин, вы можете найти этот поиск очень долгим.

Вы можете использовать некоторые из существующих алгоритмов, которые могут дать вам довольно хорошее предположение, но я боюсь, что они все не-SQL.

Я бы предложил приблизить вашу проблему:

Создайте процедуру / запрос, который найдет ОДИН товар, который наилучшим образом соответствует запрашиваемой цене, и затем вызовите его снова для новых изменений, которые у вас есть. Не идеально, но сделает работу.

Answer 4

Я не думаю, что группа может это сделать.

Я не могу придумать лучшего способа, чем найти / попробовать все перестановки на выбранном вами языке программирования или с помощью хранимой процедуры.

если бы у вас было больше 30 $, вы могли бы их опустить.

будут некоторые улучшения, если вы захотите «лучший» вариант по некоторым критериям.