程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 更多編程語言 >> 編程綜合問答 >> 直方圖-如何用動態規劃解決平面上的n個點用k個矩形覆蓋的最小面積?

直方圖-如何用動態規劃解決平面上的n個點用k個矩形覆蓋的最小面積?

編輯:編程綜合問答
如何用動態規劃解決平面上的n個點用k個矩形覆蓋的最小面積?

假設有n個點,我們要用k個矩形去覆蓋所用的點,然後這k個矩形的面積要盡可能小
1)矩形的底是在x軸上的(其實就是直方圖)
2)矩形的面積可以為0(就是一條與x軸垂直的線)
3)矩形不能重疊(邊線與頂點也都不能重合)

有人可以幫我一下嗎?想了半天都沒想出來怎麼用動態規劃解決這個問題

最佳回答:


將 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)

pierce0502
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved