How to rationally count greenhouses (the cucumber problem)?

Question

Programming

There is a task:
"A field of nxm square cells is given, each of which can contain cucumber plantations. It is necessary to build greenhouses that cover cucumbers. Greenhouses can only be rectangular, only with sides parallel to the sides of the field. The cost of building one greenhouse consists of two components - known constant and a value proportional to the area of ​​the greenhouse. A greenhouse can cover only an integer number of cells. Find out which options for building greenhouses are the least expensive, provided that all cells with cucumbers are closed from the weather."
The only question is: are there options not with a simple enumeration "on the forehead", but more rational algorithms for solving the problem? Google just gave me a link here. I would be glad if you tell me what topic this basically refers to (decision by graphs or am I completely in the wrong jungle?)

Answer 1

An interesting task. I would look in the direction of the distribution of the density of cucumbers across the field with the construction of greenhouses in these centers and in other local maxima (there is a search for maxima).
Or would use clustering algorithms to group close cucumbers. Here, for example, is an article on Habré habrahabr.ru/post/101338