#algorithm #sorting #data-structures #knapsack-problem
Вопрос:
Предположил, что у меня большое хранилище с большим количеством продуктов, и на каждой полке в моем хранилище может храниться максимум k элементов. У меня также есть длинный список с деталями заказа (каждый заказ может включать в себя множество различных продуктов)
Теперь мне нужно написать алгоритм, который получит сведения о списке заказов в качестве входных данных и вернет лучший способ организации моего хранилища.
Алгоритм должен следовать условиям:
- Разделение моих товаров на полки (подгруппы размера k)
- Продукты, которые обычно собираются вместе, стоя на одной полке
Я думал о двойной хэш-карте <имя_продукта,<имя_продукта, счетчик><имя_продукта, счетчик>>, когда каждый продукт содержит другую хэш-карту, в которой содержатся все продукты, поставляемые с ним, и подсчитываю, сколько раз она поставлялась с ним, но мне все еще трудно разделить ее на подгруппы размером k. А ты как думаешь? Есть ли лучший алгоритм для его организации или, может быть, библиотека, которая делает это?
Ответ №1:
По сути, это разбиение на гиперграфы (с целью подключения и жестким ограничением количества узлов в каждой части вместо требования к k приблизительно сбалансированным частям). Это позволит оптимизировать среднее количество полок, необходимых для каждого заказа. Существуют различные библиотеки; KaHyPar, вероятно, является лучшим в настоящее время.
Комментарии:
1. Эй! Спасибо. Для кого-то нового в этой области, как вы рекомендуете подойти к этой проблеме? Я знаю простой график, но решаю проблему с помощью
2. @almogTovim, ты мог бы сделать простой жадный алгоритм. Чтобы выбрать следующую полку: первый товар-это тот, который (из оставшихся товаров) появляется в большинстве заказов. Чтобы выбрать каждый последующий товар на полке, объедините заказы, содержащие какой-либо товар, уже находящийся на полке, и выберите товар, который еще не находится на полке, который появляется в наибольшем количестве этих заказов.