Jump to content
СофтФорум - всё о компьютерах и не только

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


Бумер
 Share

Recommended Posts

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

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

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

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

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

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

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

Link to comment
Share on other sites

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

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

  • 1 month later...

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

Link to comment
Share on other sites

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

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

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

Link to comment
Share on other sites

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

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

Link to comment
Share on other sites

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

Link to comment
Share on other sites

Бумер

Ну, мы же (и по ссылке) не добиваемся максимально плотной упаковки, весь алгоритм приведен в исходном тексте страницы, на которую ты ссылаешься. Он именно такой, какой посоветовала 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;  }

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

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

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

Edited by Тролль
Link to comment
Share on other sites

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

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

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...