Какой алгоритм использовать?

[Бумер]

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

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

Также нужно учитывать габаритные размеры товаров и вместимость ячейки.

Нельзя в одну ячейку складывать разнородные товары.

Первое что в голову приходит - задача о рюкзаках (вот здесь есть описание http://fivt.fizteh.ru/conf/in_prac_08/In_prac_faki/m_3rhfj7/m_3rhngn.html). может есть лучшее решение данной задачи?

[Yezhishe]

С точки зрения рационального торговца - это неправильный подход. Наиболее часто покупаемое надо располагать дальше от касс. А нужно это для того, чтобы идущие за нужным\часто покупаемым - по пути увидели и прихватили то, чего покупать не собирались...

[Тролль]

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

Самое сложное - это разместить товары по ячейкам с максимальной плотностью. Это так называемая задача об упаковке в контейнеры или трехмерном рюкзаке (three-dimensional knapsack packing problem). Задача довольно сложная, хотя не новая и в Интернете есть ее рассмотрения и алгоритмы. Статья в Википедии называется "Задача об упаковке в контейнеры", там и ссылочка на статью с описанием самых простых приближенных (эвристических) алгоритмов. Есть и более сложные и эффективные алгоритмы, например, вот один с готовой реализацией на С: http://www.diku.dk/hjemmesider/ansatte/pisinger/new3dbpp/test3dbpp.c

[Бумер]

Yezhishe дело в том что нужно повысить скорость выдачи товаров, т.к. это будет склад

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

[Yezhishe]

А-а... Ну склад - это ж совсем другое дело. Кабы сразу упомянул ...

[Тролль]

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

[Бумер]

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

[mikemet]

Может объем ячейки поделить на объем 1 коробки? :blush2:

[Бумер]

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

Может существует алгоритм для подобного расчета?

http://www.intermost.ru/contents/103/ - вот здесь же как то производится расчет

[mikemet]

Ну в общем то конечно...

Тогда нужно вводить какие-то дополнительные коэффициенты,видимо,... :g:

[NatM]

@Бумер, поделить высоту ячейки на высоту коробки, аналогично с шириной и длиной. Отбросить дробное и все 3 величины перемножить.

[Тролль]

Бумер

Ну, мы же (и по ссылке) не добиваемся максимально плотной упаковки, весь алгоритм приведен в исходном тексте страницы, на которую ты ссылаешься. Он именно такой, какой посоветовала NatM:

function CalcTotal(l,w,h)  {  	return (window.Container.DoorWidth > w && window.Container.DoorHeight > h) ?  		Math.floor(  		 	  Math.floor(window.Container.Width/w)  			* Math.floor(window.Container.Length/l)  			* Math.floor(window.Container.Height/h)) : -1;  }

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

У Марка Твена в автобиографической повести "Жизнь на Миссисипи" рассказывается, как хорошего лоцмана наняли за зарплату плохого - он сидел без работы и нуждался в деньгах. Капитан, видя, как его обходят другие, спросил лоцмана, почему так. Тот ответил: "Не беспокойтесь, я работаю как раз за свою зарплату" :). Зарплата тут же была увеличена ;).

Скорее всего, так же поступит и управляющий твоего магазина, правильнее рассчитывать на квалифицированного работника :).

Изменено 5 марта, 2011 пользователем Тролль

[Teddy_Bear]

Алгоритм такой -

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