Задача: как оптимально распределить остатки на складе по заказам? Коллеги, есть реальная рабочая задачка, помогите найти решение. На складе имеется n "катушек", на каждой из которых намотан кабель различной длины. Имеем m заявок на закупку кабеля, также с различной длиной. Необходимо найти оптимальную комбинацию заявок и катушек, чтобы удовлетворить максимальное (не обязательно все) кол-во заявок. При этом заявка считается закрытой только в том случае, если кабель требуемой длины поставляется полностью, одним неделимым сегментом. К примеру, если у нас есть две катушки по 15м и 20м и заявка на 21м, то удовлетворить ее не получится, потому что неделимый сегмент в 21м мы поставить не сможем.
В реальности катушек и заказов может быть под несколько сотен, и алгоритм должен отрабатывать за разумное время.
Язык программирования не принципиален, можно и просто псевдокод. Приветствуются любые ссылки на спец. литературу, в которой освещаются такого рода алгоритмы.
Задача: как оптимально распределить остатки на складе по заказам? Коллеги, есть реальная рабочая задачка, помогите найти решение. На складе имеется n "катушек", на каждой из которых намотан кабель различной длины. Имеем m заявок на закупку кабеля, также с различной длиной. Необходимо найти оптимальную комбинацию заявок и катушек, чтобы удовлетворить максимальное (не обязательно все) кол-во заявок. При этом заявка считается закрытой только в том случае, если кабель требуемой длины поставляется полностью, одним неделимым сегментом. К примеру, если у нас есть две катушки по 15м и 20м и заявка на 21м, то удовлетворить ее не получится, потому что неделимый сегмент в 21м мы поставить не сможем.
В реальности катушек и заказов может быть под несколько сотен, и алгоритм должен отрабатывать за разумное время.
Язык программирования не принципиален, можно и просто псевдокод. Приветствуются любые ссылки на спец. литературу, в которой освещаются такого рода алгоритмы.
В реальности катушек и заказов может быть под несколько сотен, и алгоритм должен отрабатывать за разумное время.
Язык программирования не принципиален, можно и просто псевдокод. Приветствуются любые ссылки на спец. литературу, в которой освещаются такого рода алгоритмы.
Похожие вопросы
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения данной задачи можно воспользоваться методом динамического программирования.
Один из возможных вариантов алгоритма:
Создать двумерный массив dp размером n+1n+1n+1 x m+1m+1m+1, где dpiiijjj будет обозначать максимальную суммарную длину кабеля, которую можно получить, используя только i первых катушек и j первых заявок.Инициализировать dp000000 = 0.Перебрать все возможные комбинации катушек и заявок и обновлять значения массива dp с учетом возможности добавления следующей катушки или заявки.На последнем этапе выбрать максимальное значение из dpnnnmmm.Алгоритм будет работать за On∗mn * mn∗m времени, что может быть приемлемо даже для большого количества катушек и заявок.
Также можно посмотреть на алгоритмы поиска оптимального назначения например,венгерскийалгоритмнапример, венгерский алгоритмнапример,венгерскийалгоритм, которые могут быть адаптированы для данной задачи.
Поиск информации по ключевым словам "задача о рюкзаке" также может дать некоторые полезные идеи для оптимизации решения.