pva
22-09-2008, 08:34
Задача: есть сетка, укладываем по ней окошки. Каждое окошко имеет минимальный размер (рассматриваем только по вертикали). Найти минимальные размеры столбцов сетки, вмещающей все окошки. Задача относится к классу задач линейного программирования, вполне решается симплекс-методом.
c.x -> min
A.x >= b
"c", "x", "b" - векторы, "А" - матрица, "." - скалярное произведение
с = {1,1,1,....} (только единички)
A состоит только из нулей и единичек
Ну ведь есть же более эффективный способ решать такие задачи? Подскажите класс задач пжлста или ссылки... я пока вижу решение симплекс-методом, но в целых числах и с упрощённым поиском главной строчки. И ещё чем-то похоже на задачу коммивояжера, только условие экстремума наоборот
c.x -> min
A.x >= b
"c", "x", "b" - векторы, "А" - матрица, "." - скалярное произведение
с = {1,1,1,....} (только единички)
A состоит только из нулей и единичек
Ну ведь есть же более эффективный способ решать такие задачи? Подскажите класс задач пжлста или ссылки... я пока вижу решение симплекс-методом, но в целых числах и с упрощённым поиском главной строчки. И ещё чем-то похоже на задачу коммивояжера, только условие экстремума наоборот