Вход | Регистрация


Информационные технологии :: Математика и алгоритмы

Как оптимально достать предметы из разных ящиков?

Как оптимально достать предметы из разных ящиков?
Я
   BlackJack
 
01.04.18 - 17:32
Дано: n одинаковых предметов известным образом размещены в m пронумерованных ящиках. Пустых ящиков нет. Нужно достать k таких предметов, причём операция извлечения для разных ящиков имеет разный вес. Есть ли оптимальный алгоритм извлечения предметов, чтобы суммарный вес был минимальным ?
 
 
   Lama12
 
1 - 01.04.18 - 17:40
(0) Так извлекай все k предметов из самого дешевого ящика.
   BlackJack
 
2 - 01.04.18 - 17:48
(1) а если там нет столько предметов?
   BlackJack
 
3 - 01.04.18 - 17:52
Важное замечание. Нужное количество предметов из ящика извлекается разом. Т.е. вес операции зависит от ящика, но не зависит от количества извлекаемых из него предметов. Поэтому могут быть ситуации, что лучше извлечь сразу два предмета из более дорогого ящика, чем по одному предмету из двух дешёвых ящиков.
   Zhuravlik
 
4 - 02.04.18 - 01:54
Похоже на жадный рюкзак, которым я недавно страдал... Только решал задачу без весов. Гугли жадный рюкзак - на ютубе есть пара лекций, но надо мозг немного прожарить.
   Куникулус
 
5 - 02.04.18 - 06:40
(3)

Ну и в чем проблема? Считаешь себестоимость ящиков, сортируешь в пордке возрастания. И начинаешь обходить. Если количество в ящике больше чем k - пропускаешь(для ускорения можно удалить из списка этот ящик), иначе открываешь ящик и уменьшаешь k на количество из ящика и возвращаешься в начало обхода.
   Куникулус
 
6 - 02.04.18 - 06:40
(5) + сортируешь в порядке возрастания себестоимости.
   Лодырь
 
7 - 02.04.18 - 06:46
(0) Задача разовая? В смысле надо достать 1 раз k1 предметов и все? Или потом будет k2,k3,k4 и так далее. Стратегии возможно разные.
   Михаил Козлов
 
8 - 02.04.18 - 09:24
(5) Проблема в (3): в 1-ом (дешевом) ящике - 1 предмет, во 2-ом (дорогом) - 2. Нужно отобрать 2 предмета.
Если действовать жадным - получим 1 предмет из 1-ого, второй - из 2-ого. В результате может получиться дороже, чем 2 из 2-ого.
   Куникулус
 
9 - 02.04.18 - 09:30
(8) Объясняю, что значит слова: "считаешь себестоимость" - делишь цену ящика на количество. Сортируешь поэтому параметру и обходишь список.
   Михаил Козлов
 
10 - 02.04.18 - 09:52
(9) Тогда это будет не исходная задача, т.к. выборка 1 ящика из 2-ого будет в 2 раза дешевле.
 
 Рекламное место пустует
   Сияющий в темноте
 
11 - 02.04.18 - 10:24
Там не все так просто,могут быть варианты.
В общем случае,задача решается полным перебором.
например,может быть один дорогой ящик на 5 пиедметов,а два более дещевых на 2 и на 3 дадут тоже количество,но при меньших затратах

полный перебор можно рассмотреть,если каждый ящик обозначить битом,мы будем выбирать одно число из большого количества бит,но можно исключить участки перебора,просто добавляя младшие ящики,пока сумма не даст нужную
   Михаил Козлов
 
12 - 02.04.18 - 10:40
Похоже на что-то складское: набрать нужное количество из разных ячеек. Озвучьте характерные параметры в реальной ситуации:
- сколько может быть различных ящиков m;
- порядок k;
- насколько сильно могут отличаться "стоимости".
Может быть реально решить полным перебором или эффективно применить схему ветвей и границ.
Навскидку не приходит на ум какая-либо из "классических" переборных задач.
   Куникулус
 
13 - 02.04.18 - 10:42
(10) Приведи конретный приме с количеством, ос стоимостями.
   Куникулус
 
14 - 02.04.18 - 10:50
(11) > Там не все так просто,могут быть варианты.

Могут. Допустим если осталось подобрать 1шт., а остались ящики в которых по 5-10 штук, а можно некоторым сочетанием подобрать точно к. Но ресурсов потребуется больше.

Но полный перебор ресурсов затребует больше.
   BlackJack
 
15 - 02.04.18 - 11:53
(12) Да, это складское. Товар раскидан по стеллажам. Некоторые коробки прямо под носом, а за некоторыми нужно далеко залезть. Но если, например, нужно отгрузить 10 штук, а в близких ("дешёвых") коробках осталось по 1 штуке, что вполне возможно, т.к. они самые ходовые, то проще один раз залезть в полную дальнюю ("дорогую") коробку и достать всё скопом, чем собирать по одной штуке из десяти ближних коробок.
   RomanYS
 
16 - 02.04.18 - 12:02
(15) тогда да,
- сортируешь по стоимости на единицу
- набираешь нужное
- если последней коробкой взял лишнего, проверяешь можно ли выкинуть набранные ранее (здесь возможно будет перебор)

Ну и, учитывая специфику, на абсолютную оптимальность здесь можно забить.
   Михаил Козлов
 
17 - 02.04.18 - 12:22
(15) Вряд ли овчинка стоит выделки (пытаться найти оптимальное решение).
Складские работники могут исходить из других соображений: например, порядок на складе.
В качестве "прототипа", наверное, вполне подойдет "жадный" из (5).
   BlackJack
 
18 - 02.04.18 - 12:46
(4) За наводку спасибо. Как оказалось, простого решения нет. Посмотрю, стоит ли реализовывать "рюкзак". Скорее всего сделаю  сортировку и перебор первых вариантов.
   RomanYS
 
19 - 02.04.18 - 12:49
(18) Рюкзак это когда ты из ящика забираешь всё, в твоей задаче ты берешь сколько надо (только платишь за всё). ИМХО это совсем не "рюкзак".
   Куникулус
 
20 - 02.04.18 - 13:25
(19) Давайте решим под-задачу:

Есть три ящика,
в одном Р деталей,
в другом О деталей.
в третьем Т деталей


Стоимость  одной детали Х, цена открытия первого ящика Р*X
Стоимость  одной детали У, цена открытия второго ящика О*У
Стоимость  одной детали Я, цена открытия второго ящика Т*Я

Х<У<Я

Понятно, что может быть такое сочетание когда лучше взять не из самого дешевого.

Вопрос: может ли быть такая ситуация когда выгоднее брать частично из двух ящиков. Или оптимальный лагоритм предполагает, что частично нужно брать только из одного ящика.
   RomanYS
 
21 - 02.04.18 - 13:35
(20) Для каждого оптимального значения стоимости будет существовать решение с не более чем одним частичным взятием. При этом могут быть решения с несколькими частичными взятиями для той же суммы.
   Михаил Козлов
 
22 - 02.04.18 - 13:38
Видимо, можно предположить, что есть оптимальное решение, в котором частично берется только из ОДНОГО ящика.
Примерно так: пусть есть решение (х1,х2,х3) и х1<Р и х2<О (взяли не полностью).
Тогда решение (Р,х1+х2-Р,х3) имеет не большую стоимость (перекинули часть из 2 в 1).
   Куникулус
 
23 - 02.04.18 - 13:38
(21) ПРимер?
   Куникулус
 
24 - 02.04.18 - 13:47
(21) Так в каком варианте может быть выгодно взять из двух ящиков частично?
   Михаил Козлов
 
25 - 02.04.18 - 13:51
(24) Похоже, что ни в каком.
   Куникулус
 
26 - 02.04.18 - 13:53
(25) Значит это возвращается нас к обычному перебору.
   RomanYS
 
27 - 02.04.18 - 14:04
(24) Ответом по сути является набор ящиков (возможно не единственный). Если в этих ящиков перебор (в смысле превышение цели), то абсолютно без разницы (в рамках данной задачи) в скольких/какой/каких ящиках оставить излишек. Если товар сыпучий можно в каждом по чуть-чуть оставить. НО заведомо можно оставить излишек в одном ящике, иначе можно обойтись без этого ящика.
   1Садовник
 
28 - 02.04.18 - 14:24
Отсортировать все ящики по весу (слева дешевые, справа дорогие):

1) набрать товар из самых дешевых ящиков (слева на право)
2) попробовать взять ВЕСЬ ("К") товар из одного ящика (если такое возможно и если ящиков несколько - берем из самого дешевого)

3) уменьшить количество товара "К"  на число товара в самом дешевом ящике (самом левом), пока "К">0 выполнять 1) и 2).

Веса в 1) и 2) запоминать для каждой комбинации. Выбрать минимальный вес из получившегося результата. Ну и проверку на "зацикливание" не забыть)
   Garykom
 
29 - 02.04.18 - 14:27
   Куникулус
 
30 - 02.04.18 - 14:38
(27) ещё раз: приведи частный пример при котором  не существует равно тли более оптимального решени в котором частично используется только один ящик, чем то в котором берётся частично из двух и более.
   RomanYS
 
31 - 02.04.18 - 14:51
(30) ещё раз: равнооптимальные решения существуют. Среди них обязательно есть решение (скорее несколько) с одним частичном ящиком, кроме случая с попаданием в цель без излишка.

Есть ощущение, что мы друг друга не понимаем.
   Михаил Козлов
 
32 - 02.04.18 - 15:32
(29) Так сформулируйте задачу ТС как задачу ЛП: у меня не получается.
   Куникулус
 
33 - 02.04.18 - 17:47
(31)> авнооптимальные решения существуют.

Ну и кому они нужны?

Ты написал:
> в твоей задаче ты берешь сколько надо (только платишь за всё). ИМХО это совсем не "рюкзак".

Если более оптимальных решений - нет. То все решается простым перебором.
 
 
   Сияющий в темноте
 
34 - 02.04.18 - 20:19
Если мы говорим о складском учете,то в оптимизацию нужно еще и статистику использования включать,иначе может оказаться,чтр текущая отгрузка будет дешевле,но потом,чего бы ни спросили,придется лезть в дальние ящик
   BlackJack
 
35 - 02.04.18 - 20:26
Остановился на таком варианте. Сортирую ячейки по возрастанию веса. Потом делаю не более 6! перестановок. Для практической задачи этого д.б. достаточно. Обычно товары лежат в нескольких ячейках, максимум 9.

Ниже алгоритм перестановок. Он не делает перестановки в лексикографическом порядке, но в целом близок к нему и стартует с отсортированной комбинации.

Процедура КнопкаВыполнитьНажатие(Кнопка)
    КолвоСтрок=5;
    
    a=Новый ТаблицаЗначений;
    a.Колонки.Добавить("Буква");
    
    Для й=1 По КолвоСтрок Цикл
        a.Добавить();
        a[й-1].Буква=й;
    КонецЦикла;
    
    generate(a,0,КолвоСтрок);
КонецПроцедуры

Процедура generate(a,t,n)
    if t=n-1 Тогда //Вывод очередной перестановки
        Текст="";
        Для й=1 По n Цикл
            Текст=Текст+a[й-1].Буква;
        КонецЦикла;
        Сообщить(Текст);
    Иначе
        Для j=t По n-1 Цикл //Запускаем процесс обмена
            Если j<>t Тогда
                a.Сдвинуть(a[j],t-j);
                a.Сдвинуть(a[t+1],j-t-1);
            КонецЕсли;
            t=t+1;
            
            generate(a,t,n); //Рекурсивный вызов
            
            t=t-1;
            Если j<>t Тогда
                a.Сдвинуть(a[j],t-j);
                a.Сдвинуть(a[t+1],j-t-1);
            КонецЕсли;
        КонецЦикла;
    КонецЕсли;
КонецПроцедуры
   Куникулус
 
36 - 02.04.18 - 20:36
(35) > максимум 9.

512вариантов для полного перебора. С возвратом назад и того меньше.

Перебертся за смешное время. Ладно бы речь шла о 100.
   BlackJack
 
37 - 02.04.18 - 20:57
9!=362880
   ndv76
 
38 - 03.04.18 - 08:25
Все равно кладовщик будет пользоваться старым добрым FIFO (или LIFO).


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.
Тема не обновлялась длительное время, и была помечена как архивная. Добавление сообщений невозможно.
Но вы можете создать новую ветку и вам обязательно ответят!
Каждый час на Волшебном форуме бывает более 2000 человек.
Рекламное место пустует