Подскажите алгоритмик

← →
Milz (2002-08-21 14:30) [0]

Задача такая.
Есть N величин - требуемое расстояния между элементами конструкции (массив А) и номенклатура (размер, количество штук) втулок-проставок между этими элементами (массив Б). Надо подобрать втулки c учётом ограничений.
1. сумма размеров втулок должна равняться размеру из массива А или отличаться не более чем на m
2. количество втулок из которых складывается размер из массива А должно быть не более n
3. общее количество использующихся втулок должно быть по возможности минимальным.
4. втулки берутся из массива Б, дать сообщение если определённого размера не хватает (как самого размера, так и количества втулок данного размера)

Т.е. задача о назначениях с ограничениями. Переборный алгоритм не устраивает т.к. слишком много данных. 3-е ограничение может выполняться не точно.

← →
Mike B. (2002-08-21 14:37) [1]

Может какой-нибудь вариант симплекс-метода подойдет?
Хотя я не уверен.

← →
Romkin (2002-08-21 16:14) [2]

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

Подскажите алгоритмик Найти похожие ветки