Ищите чистый, эффективный способ сопоставления набора данных с известными шаблонами

Question

Использование php5.2 и MySQL 4.1.22

Я столкнулся с чем-то, что поначалу казалось простым, но с тех пор уклонялось от меня в отношении простого, чистого решения.

У нас есть заранее определенные «пакеты» продукта. Упаковка 1 может содержать продукты A, B и C. В упаковке 2 могут быть буквы A, C, D и G и т. Д. Размеры упаковок варьируются от 3 до 5 продуктов.

Теперь клиент может выбрать любые 10 доступных продуктов и сделать «индивидуальную» упаковку. Поскольку у нас уже есть определенные предопределенные пакеты, мы хотели бы создать пользовательский пакет с меньшими существующими пакетами (для удобства доставки), где это возможно.

Так, например, клиент выбирает для создания «пользовательский пакет» продуктов A, B, C, D, E и F. У нас уже есть предопределенный пакет, который содержит A, B и C, называемый Foo. Таким образом, порядок будет Foo, D, E и F.

Уловка заключается в том, что наименьшее количество отдельных предметов сопровождается наименьшим количеством упаковок. Например:

Специальная упаковка: A, B, C, D, E, F, G, H, I, J.

Предопределенный пакет (1): A, B, C, D, E

Предопределенный пакет (2): A, B, C

Предопределенный пакет (3): D, E, F

Если я просто беру наибольшее совпадение, то у меня есть 1 (5 шт.) Пакет и 5 отдельных предметов. Ни Пакет (2), ни (3) не могут быть собраны с остальными предметами.

Если я загляну глубже, я обнаружу, что не собирая package (1), я могу вместо этого собрать package (2) и package (3). Это означает, что у меня есть 2 пакета и 4 отдельных предмета (лучший выбор в этом правиле бизнеса).

Поскольку я использую MySQL, я ограничен в наличии только одного слоя суб-выбора (насколько мне известно). Так что этот вид нужно будет выполнить в php. Я рассмотрел использование array_intersect () для определения совпадений, но каждый найденный мной способ экспоненциально растет по отношению к обработке, так как число предопределенных пакетов растет линейно.

Я проверил это парой других друзей-программистов и снова, хотя казалось, что должен быть простой ответ, который мы все обнаружили, что это не так просто, как кажется. Итак, я думал, что выложу это здесь как хороший носилки с лапшой. Большое спасибо за ваше время!

Answer 1

Проблема, как правило, "сложная" (если говорить о сложности вычислений). На самом деле, у меня в голове звучит колокольчик, который, вероятно, сводится к одной из тех классических проблем алгоритма, как проблема с рюкзаком , но я не могу присвоить ему правильное имя.

Однако, с таким небольшим проблемным пространством (они могут выбрать только 10 продуктов), это должно быть довольно быстро, просто перебрать вещь. Когда кто-то отправляет пользовательскую сборку, просто рекурсивно атакуйте ее всеми возможными способами и посмотрите, какая из них лучше.

То есть, возьмите выбранные компоненты и сначала попытайтесь удалить из него компоненты «Пакета 1». Если это возможно, возьмите оставшиеся компоненты и попытайтесь извлечь из него компоненты «Пакета 2» и т. Д. Следите за наилучшим решением, которое вы нашли, на протяжении всего процесса.

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

---

Отредактировано, чтобы добавить:

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

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

Answer 2

Извините, что усложнил вашу проблему. : -)

Несмотря на то, что вам может потребоваться предварительный расчет возможных решений или же потребители сами выбирают из предварительно определенных пакетов: что, если предварительно определенного пакета больше нет в наличии?

Что если не существует решения для завершения заказа в это время? После этого вы отправите часть заказа и, если да, включите ли вы отдельные товары, даже если будете знать, что через некоторое время вы сможете выбрать предопределенный пакет?

И действительно ли вы уверены, что предопределенным пакетам не будет назначено какое-либо «предпочтение»? Например, какой предопределенный пакет выбрать при заказе «ABCD», а предопределенные пакеты «ABC» и «BCD» существуют? Если, например, вы знаете, что предварительно определенного пакета «ABC» часто нет в наличии, то, возможно, из-за этого предпочтение будет отдано «BCD».

Итак: возможно, вам нужно использовать какое-то моделирование, в котором вы можете легко изменить некоторые жестко запрограммированные правила, а не пытаться найти автоматизированное решение. Конечно, это может быть сам PHP.

Answer 3

Предлагаю вам помочь клиенту. На экранах выбора продукта покажите, какие упакованные наборы доступны, и дайте им возможность составлять комбинации (оцененные по цене, чтобы сумма одних была достаточной для покрытия специальной обработки).