pierce0502
pierce0502
采纳率100%
2015-03-07 02:51

如何用动态规划解决平面上的n个点用k个矩形覆盖的最小面积?

已采纳

假设有n个点,我们要用k个矩形去覆盖所用的点,然后这k个矩形的面积要尽可能小
1)矩形的底是在x轴上的(其实就是直方图)
2)矩形的面积可以为0(就是一条与x轴垂直的线)
3)矩形不能重叠(边线与顶点也都不能重合)

有人可以帮我一下吗?想了半天都没想出来怎么用动态规划解决这个问题

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

4条回答

  • xuzuning xuzuning 6年前

    将 n 个点的坐标排序(x 为主键)

    任取一点将 n 个点分成 2 组 n1 和 n2,求出 2 个面积 m1 和 m2

    从 n1 中取出最后的一个点,放入 n2 中,再求出 2 个面积 m'1 和 m'2

    如果 m'1+m'2 < m1+m2,则继续

    分别对重组后的 n1 和 n2 做如上操作

    直至满足 k 的数量要求,反之亦然

    其实你很快就会发现最小面积就是前 k-1 个点的 (maxx - minx)*(maxy-miny) + (n-k-1)

    点赞 评论 复制链接分享
  • xuzuning xuzuning 6年前

    又想了一下,其实我说的也不对,最小面积应该是 d * N,d>=1

    其实是你缺少了一个先决条件: k < n

    点赞 评论 复制链接分享
  • xuzuning xuzuning 6年前

    ∑Yi 是所有点到 X 轴的距离。设点的直径为 1,则 1*∑Yi 就是所有矩形的最小面积之和

    同理,∑Xi 也是

    由于你不允许矩形相交,所以只能取 ∑Yi 或 ∑Xi 的小者

    点赞 评论 复制链接分享
  • xuzuning xuzuning 6年前

    ∑Xi 或 ∑Yi 就是

    什么规划都不需要

    点赞 评论 复制链接分享