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


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

Метки: 

Подскажите алгоритм - как собрать список товаров из прайса на минимальную цену

Я
   LienXo
 
24.07.18 - 22:56
Есть список необходимых товаров (до 50 позиций). Каждый товар нужен по 1 штуке. Есть прайс, состоящий из номенклатуры-наборов. Т.е. номенклатура из прайса может состоять из одного или нескольких требуемых товаров. Один товар не встречается чаще чем в 10 номенклатурах. Необходимо собрать список номенклатуры, включающей весь список товаров (допускается попадание товара 2 и более раз) на минимальную сумму.
 
  Рекламное место пустует
   PR
 
1 - 24.07.18 - 22:57
Так так. И как сделал?
   LienXo
 
2 - 24.07.18 - 22:59
(1) если бы сделал - не спрашивал :) Тупым перебором - лень, ищу легких путей
   PR
 
3 - 24.07.18 - 23:02
(2) А, так это вопрос :))
А то вопросительных знаков просто не видно :))
   LienXo
 
4 - 24.07.18 - 23:04
(3) Думал слова "подскажите" в заголовке будет достаточно
   PR
 
5 - 24.07.18 - 23:08
(4) Схалтурить думал? :))
   Garykom
 
6 - 24.07.18 - 23:08
Алгоритма ускоряющего подбор одного списка товаров нет.

Но возможны алгоритмы с предобработкой прайсов (номенклатур-наборов), чтобы затем быстро подбирать требуемые по списку товары.
   PR
 
7 - 24.07.18 - 23:10
А откуда такая задача-то?
   Garykom
 
8 - 24.07.18 - 23:12
Делаешь полный перебор сочетаний номенклатур (пересечений множеств товаров) так чтобы создать/выбрать более крупные наборы включающие минимум пересекающихся товаров.

Затем входной список товаров банально в списке товаров, где лучше соответствие то и берешь и добиваешь одиночными номенклатурами или 2-ми, 3-ми и т.д. как получится.
   LienXo
 
9 - 24.07.18 - 23:14
(8) наиболее крупные не всегда проходят - например два парных товара могут оказаться (ну вот такой прайс) дешевле группы из четырех, в которую они входят.
   Garykom
 
10 - 24.07.18 - 23:15
(9) Тьфу у тебя минимизация по отдельному параметру - цене а не кол-ву.
 
 
   LienXo
 
11 - 24.07.18 - 23:15
+(9) не два парных а две пары. Типа печенька+конфетка = рупь и яблоко +банан = рупь. А все четыре вместе - 3 рубля.
   LienXo
 
12 - 24.07.18 - 23:19
(7) поликлиника - профосмотры.
   PR
 
13 - 24.07.18 - 23:20
Куча вложенных циклов
Первый по номенклатуре, в которой есть товар1
Второй по номенклатуре, в которой есть товар2
И так далее
В случае, если товарN уже есть в набранных товарах, то пропускаем
   LienXo
 
14 - 24.07.18 - 23:22
(13) я же в 2 сказал - перебором можно, хотел че нить из высшей математики, счас так модно :)
   Garykom
 
15 - 24.07.18 - 23:23
(13) Перебором "до 50 позиций" будет пипец как долго.
   PR
 
16 - 24.07.18 - 23:23
(14) Так тут только перебор
   PR
 
17 - 24.07.18 - 23:24
(15) Ну таки да, а что делать?
   LienXo
 
18 - 24.07.18 - 23:24
(15) надеялся что нить типа "рюкзака" всплывет. Просто основы анализа так давно проходил... мимо...
   PR
 
19 - 24.07.18 - 23:25
+(17) 10^50 по максимуму так-то, да :))
   RomanYS
 
20 - 24.07.18 - 23:28
(12) номенклатура это врачи?
   Garykom
 
21 - 24.07.18 - 23:29
Попробуй для начала деревья из номенклатур-наборов построить и глянуть ветвистость.

"Типа печенька+конфетка = рупь и яблоко +банан = рупь. А все четыре вместе - 3 рубля."

"печенька+конфетка" и "яблоко+банан" входят в "все четыре вместе" и т.д.

затем откинуть те в которых крупный набор дороже чем сочетание мелких
   Garykom
 
22 - 24.07.18 - 23:31
(20) Думаешь цель минимальным кол-вом врачей закрыть максимум специальностей/услуг и как можно дешевле?
   LienXo
 
23 - 24.07.18 - 23:31
(20) нет. Анализы. Врач - всегда один в номенклатуре
   Garykom
 
24 - 24.07.18 - 23:32
Минимизация по затратам на зп врачей ))
   RomanYS
 
25 - 24.07.18 - 23:33
(23) они что какими-то комплексами идут? 50 анализов? Вы космонавтов обследуете?
   LienXo
 
26 - 24.07.18 - 23:33
(24) Если бы - глупое пожелание заказчика минимизировать счет клиенту :)
   Garykom
 
27 - 24.07.18 - 23:34
А может просто прайс лист заставить поменять? На нормальный без наборов а одиночные только.
   RomanYS
 
28 - 24.07.18 - 23:34
(26) Добавить в прайс комплекс из 50 анализов не предлагали?
   LienXo
 
29 - 24.07.18 - 23:34
(25) Ты не поверишь какие требования у минздрава к нянечкам в детсадах :)
   Garykom
 
30 - 24.07.18 - 23:38
Кстати задачка идеальна для тупого параллельного перебора - на GPU (OpenCL или CUDA).
   Garykom
 
31 - 24.07.18 - 23:39
(30)+ Любая новая видяшка (из ныне продающихся) уже умеет из коробки OpenCL (почти все) или CUDA (nvidia)
   Asmody
 
32 - 24.07.18 - 23:44
   PR
 
33 - 24.07.18 - 23:45
Хотя..., может как-то так...

Берем набор из десяти наиболее дешевых товаров, где в первой номенклатуре есть товар1, во-второй есть товар2 и т. д.
Фиксируем текущую минимальную стоимость

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

После этого пробуем перебор с отсечением ветки в случае, если новая стоимость выше или равна минимальной
 
  Рекламное место пустует
   PR
 
34 - 24.07.18 - 23:50
Да, это вам не задачки 1Сергея для начальной школы :))
   Asmody
 
35 - 24.07.18 - 23:59
(32)+ Если товар попадает в набор точно один или ноль раз, то это задача 0-1 ЦЛП. Немного проще, но не сильно.
Задача NP-полная, алгоритмов для нее масса. И точные, и эвристические. Всё есть в Яндексе.
   Garykom
 
36 - 25.07.18 - 00:10
   Garykom
 
37 - 25.07.18 - 00:10
   Garykom
 
38 - 25.07.18 - 00:12
   Garykom
 
39 - 25.07.18 - 00:14
"На классах задач, где n или m ограничены константой, задача за полиномиальное время решается методами полного перебора."

Хочешь точное решение - только полный перебор ))
   Сияющий в темноте
 
40 - 25.07.18 - 09:39
Наборы можно разбить на группы,если можно выделить непересекающиеся группы наборов,это сильно уменьшит перебор.
И еще,нужно понимать,что иногда для решения придется допустить брать лишние товары,если,например,нам нужен банан и вишенка,которые по два рубля,а набор банан,вишенка и яблоко три
   Михаил Козлов
 
41 - 25.07.18 - 10:06
(28) Присоединяюсь. И повторений не будет: как-то странно будет выглядеть счет, где придется 2 раза сдавать кал.
   Сияющий в темноте
 
42 - 25.07.18 - 10:52
Наборы можно разбить на группы,если можно выделить непересекающиеся группы наборов,это сильно уменьшит перебор.
И еще,нужно понимать,что иногда для решения придется допустить брать лишние товары,если,например,нам нужен банан и вишенка,которые по два рубля,а набор банан,вишенка и яблоко три
если упорядочить товары,то перебор можно сильно сузить,перебирая только группы,где нет товаров с меньшим кодом,состоящим в списке,но тогда придется делать захват групп с товаром,даже если его выбрали ранее,т.к.иначе можно пропустить группу или ставить у товара признак перебираемый,если по нему идет перебор и отбрасывать группы с товарами,которые идут раньше и перебираемые
   Asmody
 
43 - 25.07.18 - 10:58
(41) Тебе сложно штоль?
   NSSerg
 
44 - 25.07.18 - 11:01
(42) Сейчас так-же в например в Хеликсе, когда сдаешь кровь - зачастую делаешь лишние анализы, так как в наборе дешевле.
   Михаил Козлов
 
45 - 25.07.18 - 11:07
(43) В смысле алгоритм найти/придумать или кал сдать?
После 5-ого курса были военные лагеря. Так вот один однокашник впервые сходил по большому через 3 недели.
Так что разные бывают ситуации.
   Кирпич
 
46 - 25.07.18 - 11:15
похоже на задачку c sql-ex.ru
   Михаил Козлов
 
47 - 27.07.18 - 13:07
Может быть попробовать другую постановку задачи:
определить стоимость каждого анализа с условием, что сумма
анализов входящих в набор = стоимости набора (из прайса) и сумма стоимостей всех анализов - минимальна.
Искомые переменные: Xi - стоимость i-того анализа
Ограничения:
1. Xi>=0
2. СУММА(Xi по входящим в набор j) = Цj (цена набора из прайса) (для всех j)
3. СУММА(Xi) -> MIN

Это задача линейного программирования. Реализация симплекса метода на 1С есть - могу выслать.
Задача специальной структуры - может можно свести к потоку в сети.



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