Задача об огурцах.
Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами, параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной и величины, пропорциональной площади парника. Парник может накрывать только целое количество ячеек. Выяснить какие варианты строительства парников наименее затратны при условии, что закрытыми от непогоды оказываются все ячейки с огурцами.
// В общем подскажите в какую сторону двигаться.
Что я надумал?
У нас есть коэффициент плотности огурцов это кол-во огурцов делить на всего клеток. И вот мы выбираем такие места для парников, что оказываются максимальными по размеру И коэффициент плотности в них БОЛЬШЕ или РАВЕН общему коэффициенту - это будет оптимально, НО при проходе с начала и с конца у нас получаются РАЗНЫЕ результаты и непонятно откуда начинать перебор, и в общем сложно. Кто может помогите...
изложение невнятное ... но я так понимаю (может кто захочет повозиться):
- n и m должны вводиться...
- любые рассуждения о "коэффициенте плотности огурцов" - это бред от дурного ума о ... "сферическом интеграле в вакууме" ... тут пионер просто ошибся ;-)
- конкретная конфигурация прямоугольников-посадок должна также вводится ... скажем заданием <левый-верхний-угол: X, Y>, <правый-нижний-угол: X, Y>
- ... задача может быть только конкретная - а дальше это пространство нужно "накрывать" прямоугольниками...
- похоже, что делать это самым понятным образом - рекурсивно
- и ... что-то мне подсказывает, что это будет NP-полная задача ... о рюкзачке ;-)
Олег Цилюрик: Ну, в условии написано "Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.", так что подозреваю, что m, n и распределение огурцов даётся как вводные данные для каждого запуска.
Vlad_Fedorenko: я бы рад, но полный перебор это что-то типа O((n!)^n), n - изменяется не линейно + константа. И тем более я даже не представляю себе полный перебор.
Стоимость парника #1 равна p1 = x*S1 + c
Стоимость всех парников ( с номерами от 1 до n) p = x*S1+c+ ... + x*Sn+c
Выносим константу за скобки p = x*(S1 + ... Sn) + c*n
По условию задачи сумма площадей всех парников равна площади поля. Поэтому стоимость строительства зависит от количества парников n. Чем меньше парников тем дешевле.
