2 u014354596 u014354596 于 2015.06.28 14:33 提问

用动态规划解决矩形覆盖问题

··有没有大神会那个矩阵覆盖问题啊?就是在POJ中的~~求解代码
描述
在平面上给出了n个点,现在需要用一些平行于坐标轴的矩形把这些点覆盖住。每个点都需要被覆盖,而且可以被覆盖多次。每个矩形都至少要覆盖两个点,而且处于矩形边界上的点也算作被矩形覆盖。注意:矩形的长宽都必须是正整数,也就是说矩形不能退化为线段或者点。

现在的问题是:怎样选择矩形,才能够使矩形的总面积最小。
输入
输入包括多组测试数据。每组测试数据的第一行给出n (2 <= n <= 15),表示平面上的点数。后面的n行,每行上包括两个整数x, y (-1000 <= x, y <= 1000),给出一个点在平面上的x坐标和y坐标。输入数据保证:这n个点在平面上的位置各不相同。

最后一组测试数据中n = 0,表示输入的结束,这组数据不用处理。
输出
对每一组测试数据,输出一行,包括一个正整数,给出矩形的最小总面积。

2个回答

Tiger_Zhao
Tiger_Zhao   Rxr 2015.06.29 14:18

类似求无向连通图的最小生成树算法;更简单,不需要矩形“连通”:
1)未覆盖的点集合为A、已覆盖点的集合为B,初始时n个点全在A中。
2)n个点两两生成最小覆盖矩形,矩形集合为R,按面积排序。
3)初始化总面积S=0
4)循环直到A为空:
4.1)从R中选最小的一个矩形r
4.2)如果r覆盖的点有不在B中的:点就从A移到B,累计面积 S=S+r
4.3)并从R中移除r。
5)输出S

OrdinaryCrazy
OrdinaryCrazy 对于(1,0)(1,1)(2,2)这组数据,这种方法好像不行,有可能是我理解不到位
4 个月之前 回复
OrdinaryCrazy
OrdinaryCrazy   2017.07.29 17:56
Csdn user default icon
上传中...
上传图片
插入图片