Рассчёт минимального размера
Задача: есть сетка, укладываем по ней окошки. Каждое окошко имеет минимальный размер (рассматриваем только по вертикали). Найти минимальные размеры столбцов сетки, вмещающей все окошки. Задача относится к классу задач линейного программирования, вполне решается симплекс-методом.
Код:
c.x -> min
A.x >= b
"c", "x", "b" - векторы, "А" - матрица, "." - скалярное произведение
с = {1,1,1,....} (только единички)
A состоит только из нулей и единичек
Ну ведь есть же более эффективный способ решать такие задачи? Подскажите класс задач пжлста или ссылки... я пока вижу решение симплекс-методом, но в целых числах и с упрощённым поиском главной строчки. И ещё чем-то похоже на задачу коммивояжера, только условие экстремума наоборот |
| Delirium |
22-09-2008 09:36 905395 |
Покопай здесь , вдруг найдешь что нибудь интересное. |
полезная ссылка :) немного подумав, определил что задача очень приятно решается динамическим программированием. По пути возник вопрос: есть список N записей чисел от 1 до P. Сортировка по возрастанию быстрее, чем N*P операций?
|
pva, от P не зависит (за исключением вырожденных случаев, когда P на порядки меньше N)
|
Время: 14:20.
© OSzone.net 2001-
