задача логистики, существующее решение очень долгое, готовых решений

kondrashina

Привет, не могу решить следующую задачу,
Условие: есть множество уникальных по типу элемента множеств одинаковых элементов, структура задается в виде
3 47
5 33
1 21
читать это так, что есть 3 элемента 47, 5 элементов 33, 1 элемент 21. Элемент обладает свойством - это его значение, в данном случае 47, 33 или 21.
Задача: необходимо выбирать n (например 3) элементов так, чтобы сумма их значений не превышала М (например 120). Числа n и М так же даны. В результате получится (сумма мощностей множеств)/n выборок. Они мне и нужны. Пример
n = 3
М = 120
3 47
5 33
1 21
В результате, может получиться
2 47 1 47 3 33
1 21 2 33
Я пишу может, т.к. в зависимости от алгоритма и данных могут получаться разные выборки. Как я решал эту задачу:
1 алгоритм: смотрим всевозможные выборки C(n,k) n элементов из "растянутого" массива (47, 47, 47, 33, 33, 33, 21 считаем сумму и принимаем или отметаем найденное сочетание. Побочная возможность - можно искать максимально возможную по сумме значений выборку в каждом случае, но это необязательно. Минусы: очень долго для больших чисел (n например 32, а размер растянутого массива ~900) работает этот алгоритм на С++.
2 алгоритм: рандомно выбирать сочетания, помечая выбранные, но есть проблема, что решение может быть вообще и не найдено за определенное количество попыток, их можно устремить к бесконечности, но тогда и время туда же полезет
Отдельного внимания заслуживает разработка критерия достаточности решения. Но сейчас я предполагаю, что решение существует.
Задача имеет реальное прикладное применение в логистике. Я сейчас прорабатываю еще один алгоритм, но почему-то приходит понимание, что это опять будет полный перебор как в случае 1 Помогите, пожалуйста с идеями.
Ярослав

Anna23

Расскажи, если не сложно, реальную задачу.

kondrashina

Реальная задача состоит в следующем. С точки зрения объема в вагон необходимо положить 100 стандартных ящиков, тогда они будут плотно упакованы и не будут ездить по вагону. С точки зрения массы нельзя превышать 20т. Необходимо привезти ящики разных типов разного количества. Задача состоит в том, чтобы понять, как оптимально разложить эти ящики по вагонам. Т.е. нужно выбрать по 100 ящиков так, чтобы сумма их масс была меньше 20т. Понятно объяснил?
Ярослав

FieryRush

Задача: необходимо выбирать n (например 3) элементов так, чтобы сумма их значений не превышала М (например 120). Числа n и М так же даны. В результате получится (сумма мощностей множеств)/n выборок. Они мне и нужны. Пример
Если выбираешь все такие подмножества - это экспонента.

FieryRush

Реальная задача состоит в следующем. С точки зрения объема в вагон необходимо положить 100 стандартных ящиков, тогда они будут плотно упакованы и не будут ездить по вагону. С точки зрения массы нельзя превышать 20т. Необходимо привезти ящики разных типов разного количества. Задача состоит в том, чтобы понять, как оптимально разложить эти ящики по вагонам. Т.е. нужно выбрать по 100 ящиков так, чтобы сумма их масс была меньше 20т. Понятно объяснил?
Это похоже на задачу о рюкзаке. Главное отличие - ограничение на количество.

kondrashina

Подробнее можно ? - ссылку?

MadCat

Это похоже на задачу о рюкзаке. Главное отличие - ограничение на количество.
Это не переборная задача, в отличие от задачи о рюкзаке.

Anna23

Хмм
Советую для начала съездить и посмотреть в реале как все происходит. Там же уточнить, можно ли менять ориентацию (вертеть) ящики, ставить одни на другие (предел массы на единицу площади, стоимость повреждений реальность хаотичной упаковки(допустим прога указала, совершенно фантастическую схему упаковки - каким образом она будет донесена до грузчиков вероятность изменения габаритов коробок, вследствии повреждений.
В конце концов оценить максимальную выгоду твоего начинания, поделить ее пополам(в лучшем случае оценить стоимость обслуживания этой системы, оценить изменившееся время на загрузку (если менялось оценить стоимость обучения грузчиков новой системе погрузки и посчитать надо ли оно тебе.
Понимаешь, это же не ты первый додумался. Это проблема давно существует.Слышал(но не видел что специализированные SCM системы умеют(частично) так упаковываться. Советую покопать на эту тему доки по этим системам (Пример: i2).

Santiny

imho ненужный бред
У коробок куча фишек - может меняться форма от партии к партии, опять же хрупкось/вертикальность.. Пойми, грузчикам будет легче без проги..
Сколько кто не пытался угадывать, сколько влезет в .. (контейнер, н-р.) - даже с опытом 6 лет никто не угадывал

mamishka

Ты уверен, что будет удобно потом разыскивать партию товара А из 100 коробок равномерно размазанных по 20 вагонам?

Anna23

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

Ktitiss

Можно найти минимальное число вагонов, которое точно потребуется: Max ( (общий вес груза)/M, (общее кол-во ящиков)/n). Дальше пробовать упихать в это число вагонов. Если не влезло, то добавить один вагон, и т.д. Упихивать в фиксированное число вагонов, кажется можно за линейное время. Так что в итоге сложность n^2.

kondrashina

А нет этой проблемы, т.к. все вагоны на один склад приезжают. Она может возникнуть на внутрискладовой логистике.

kondrashina

Предложение интересное поищу подумаю. Спасибо.
Оставить комментарий
Имя или ник:
Комментарий: