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

Question

Редактировать:

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

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

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

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

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

       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) создать один запрос, который возвращал бы любую возможную комбинацию элементов?

Спасибо!

a

Answer 1

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

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

Если количество элементов относительно невелико, возможно, вам удастся выполнить это методом перебора.Инструкция 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 2

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

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

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

Answer 3

я не думаю, что group by сможет это сделать.

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

если у вас были товары стоимостью более 30 долларов, вы могли бы их опустить.

были бы некоторые улучшения, если бы вы хотели получить "лучший" вариант по некоторым критериям.

Answer 4

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

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

Я бы предложил сделать аппроксимацию вашей проблемы:

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