Задача: как оптимально распределить остатки на складе по заказам?

Question

[Николай Артамонов]

Коллеги, есть реальная рабочая задачка, помогите найти решение. На складе имеется n "катушек", на каждой из которых намотан кабель различной длины. Имеем m заявок на закупку кабеля, также с различной длиной. Необходимо найти оптимальную комбинацию заявок и катушек, чтобы удовлетворить максимальное (не обязательно все) кол-во заявок. При этом заявка считается закрытой только в том случае, если кабель требуемой длины поставляется полностью, одним неделимым сегментом. К примеру, если у нас есть две катушки по 15м и 20м и заявка на 21м, то удовлетворить ее не получится, потому что неделимый сегмент в 21м мы поставить не сможем.

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

Язык программирования не принципиален, можно и просто псевдокод. Приветствуются любые ссылки на спец. литературу, в которой освещаются такого рода алгоритмы.

Answer 1

[Сергей Соколов]

Задача об упаковке в контейнеры, задача об одномерной упаковке.