Как решить задачу об огурцах?

Question

[m1greatcool]

Задача об огурцах.
Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.
Необходимо построить парники, закрывающие огурцы. Парники могут быть только прямоугольной формы, только со сторонами, параллельными сторонам поля. Стоимость строительства одного парника складывается из двух составляющих - известной постоянной и величины, пропорциональной площади парника. Парник может накрывать только целое количество ячеек. Выяснить какие варианты строительства парников наименее затратны при условии, что закрытыми от непогоды оказываются все ячейки с огурцами.
// В общем подскажите в какую сторону двигаться.
Что я надумал?
У нас есть коэффициент плотности огурцов это кол-во огурцов делить на всего клеток. И вот мы выбираем такие места для парников, что оказываются максимальными по размеру И коэффициент плотности в них БОЛЬШЕ или РАВЕН общему коэффициенту - это будет оптимально, НО при проходе с начала и с конца у нас получаются РАЗНЫЕ результаты и непонятно откуда начинать перебор, и в общем сложно. Кто может помогите...

Comments

[Vlad_Fedorenko]

Какие ограничения на все числа?

[m1greatcool]

что значит на все числа? Преподаватель ограничений не дал.

[Vlad_Fedorenko]

m1greatcool: ну тогда делайте полный перебор, пусть считает несколько дней или сколько там получится

[Олег Цилюрик]

изложение невнятное ... но я так понимаю (может кто захочет повозиться):
- n и m должны вводиться...
- любые рассуждения о "коэффициенте плотности огурцов" - это бред от дурного ума о ... "сферическом интеграле в вакууме" ... тут пионер просто ошибся ;-)
- конкретная конфигурация прямоугольников-посадок должна также вводится ... скажем заданием <левый-верхний-угол: X, Y>, <правый-нижний-угол: X, Y>
- ... задача может быть только конкретная - а дальше это пространство нужно "накрывать" прямоугольниками...
- похоже, что делать это самым понятным образом - рекурсивно
- и ... что-то мне подсказывает, что это будет NP-полная задача ... о рюкзачке ;-)

[MiiNiPaa]

Олег Цилюрик: Тут не прямоугольные посадки а булев массив "Есть огурцы"/"Нет огурцов". Что-то вроде кластеризации требуется.

[Олег Цилюрик]

MiiNiPaa:
ну тогда тем более требуется какой-то способ начального ввода фиксированной "посадки": занятых позиций матрицы n x m и свободных

[MiiNiPaa]

Олег Цилюрик: Ну, в условии написано "Задано поле n x m квадратных ячеек, в каждой из которых могут находиться посадки огурцов.", так что подозреваю, что m, n и распределение огурцов даётся как вводные данные для каждого запуска.

[m1greatcool]

Олег Цилюрик: "Формат данных разрабатывается самостоятельно": то есть я из блокнота подаю поле нулей и единиц. MiiNiPaa: спасибо за то что отвечаете

[m1greatcool]

Олег Цилюрик: "коэффициенте плотности огурцов ... бред" - почему?

[m1greatcool]

Vlad_Fedorenko: я бы рад, но полный перебор это что-то типа O((n!)^n), n - изменяется не линейно + константа. И тем более я даже не представляю себе полный перебор.

Answer 1

[Mrrl]

Если один из размеров не очень большой, например, не больше 15, сработает динамическое программирование.
Идём по полю с узкой стороны, двигая линию каждый раз на одну клетку. Для конкретной конфигурации парников у нас в каждый момент линия делится на отрезки, каждый из которых может либо принадлежать своему парнику, либо быть пустым (не покрытым парниками). При этом отрезки с парниками могут касаться друг друга, а пустые отрезки - нет, они сливаются в один. Кроме того, мы помним накопленный штраф для созданных (в том числе, закрытых) парников и их площади.
На каждом шагу мы можем:
- сначала закрыть некоторые парники (соответствующие отрезки станут пустыми)
- продлить остальные парники ещё на клетку (к штрафу добавляется число клеток этих парников)
- на пустых местах открыть новые парники (к штрафу добавляется стоимость открытия этих парников и число клеток в них).
При этом все клетки с огурцами должны оказаться закрытыми. Открывать новые парники, в которых пока нет ни одного огурца, смысла нет. Все остальные варианты должны быть рассмотрены.
Начинаем с одного пустого отрезка. На каждом шагу обрабатываем все имеющиеся конфигурации, строим их продолжения. Из эквивалентных новых конфигураций (в которых одинаковые карты отрезков) выбираем ту, у которой меньше штраф.
Всё. Осталось придумать, как дёшево хранить пройденные пути, чтобы потом восстановить результат.

Comments

[Mrrl]

Например. Пусть посадка такая:

* . .
* * .
* . *
. * *

стоимость парника - 3 дополнительных клетки.
Идём снизу. Конфигурацию будем задавать отрезками пересечения линии с парниками. Например, [1,2],[3] - линия пересекла два парника, один занял первые две клетки, другой - третью.
В начале у нас парников нет, штраф нулевой.
В первой строке мы можем построить такие конфигурации:
(A1): [1,2],[3] - штраф=9 (два парника и 3 клетки)
(A2): [1,2,3] - штраф=6
(A3): [2],[3] - штраф=8
(A4): [2,3] - штраф=5.
В следующей строке возможны конфигурации
(B1): [1],[2],[3] - штраф=14 (из A3)
(B2): [1],[3] - штраф=13 (из A3 или А4)
(B3): [1,2],[3] - штраф=12 (из A1)
(B4): [1],[2,3] - штраф=11 (из A4)
(B5): [1,2,3] - штраф=9 (из A2)
B1 может получиться только из A3 (продлили парник [2]), остальные конфигурации - из любой другой.
Строка 3:
(C1): [1],[2],[3] - штраф=17 (из B1)
(C2): [1],[2] - штраф=16 (из B1 или B4)
(C3): [1],[2,3] - штраф=14 (из B4)
(C4): [1,2],[3] - штраф=15 (из B3)
(C5): [1,2] - штраф=14 (из B3 или B5)
(C6): [1,2,3] - штраф=12 (из B5)
Последняя строка:
(D1): [1],[2],[3] - штраф=20 (из C1)
(D2): [1],[2] - штраф=18 (из C2)
(D3): [1],[2,3] - штраф=17 (из C3)
(D4): [1,2],[3] - штраф=18 (из C4)
(D5): [1,2] - штраф=16 (из C5)
(D6): [1,2,3] - штраф=15 (из C6)
(D7): [1] - штраф=15 (из C3)
(D8): [1],[3] - штраф=19 (из С1 или С3).
Таким образом, получаем две оптимальных конфигурации: либо один парник на всю площадь, либо два парника - один в левом ряду, другой в двух правых.

[m1greatcool]

Mrrl: спасибо попробую разобраться и реализовать, времени мало.

Answer 2

[MiiNiPaa]

Назовём нормализированым парник, в котором нет "пустых" границ, т.е. на верхней, нижней, правой и левой границах есть, как минимум, по одному огурцу.

Начнём с одной теплицы, охватывающей всё поле. Нормализируем её, считаем стоимость.

Рассматриваем все варианты разбиения одной прямой (проходимся по всем внутренним вертикалям, затем горизонталям). Для каждого разбиения нормализируем получившиеся теплицы, подсчитываем стоимость. Затем берём разбиение с наименьшей стоимостью. Если эта стоимость больше или равна оригинальной, оставляем оригинальную теплицу, КОНЕЦ. Иначе используем две новых теплицы и для каждой из них рекурсивно запускаем этот алгоритм.

EDIT: Не работает для всех видов полей. Контрпример в комментариях.

Comments

[Mrrl]

И что он сделает для такого поля (стоимость парника - 2 клетки)?

* * * . *
. . . . *
* . . . *
* . . . .
* . * * *

[MiiNiPaa]

Mrrl: Не заработает :(

Answer 3

[AtomKrieg]

Стоимость парника #1 равна p1 = x*S1 + c
Стоимость всех парников ( с номерами от 1 до n) p = x*S1+c+ ... + x*Sn+c
Выносим константу за скобки p = x*(S1 + ... Sn) + c*n
По условию задачи сумма площадей всех парников равна площади поля. Поэтому стоимость строительства зависит от количества парников n. Чем меньше парников тем дешевле.

Comments

[MiiNiPaa]

По условию задачи сумма площадей всех парников равна площади поля

С чего вы это взяли? Если посреди поля гордо растёт одинокий огурец, всё поле накрывать? Если два огурца в противоположных углах поля?

И вы ещё не учли случай, когда "постоянная" отрицательна. В таком случае выгодней каждому огурцу по своему парнику давать.

[m1greatcool]

Простите, но вы абсолютно не поняли задачи.

[AtomKrieg]

m1greatcool: Как описано, так и понято