我現在正在上“演算法和資料結構”課程，并且一直在解決這個問題。我希望在這里找到一些想法。
這是問題所在：
給你 2 個數字n，s它們代表點數和某個矩形的面積。然后是n每行由 2 個數字組成：代表第 i 個點的 x 和 y 坐標x_i。y_i同一坐標可能有多個點。如果發生這種情況，這些點被認為是不同的，必須進行相應的處理。
輸入約束如下：n <= 300, s <= 1,000,000，每個坐標都在 0 到 2000 之間。
該解決方案必須在 8 秒內運行并且消耗少于 512 Mb 的記憶體
問題本身就是找一些邊平行于坐標軸的矩形，兩邊都大于等于1（邊長可以是浮點數），而且面積正好s是里面有盡可能多的點這個矩形。如果一個點位于矩形內部或側面，則認為該點位于矩形內部。
作為問題的答案，我需要列印位于找到的矩形內的點的坐標。
所以，在這里我對這個問題的想法：
1）蠻力
首先，我花了一些時間來理解矩形實際上可能位于任何坐標，只要它的面積等于s. 我還發現，最“有效”（就其內部的點數而言）矩形是在其邊界上有點的矩形，因為試圖將它們完全放入其中是沒有意義的。
所以，我嘗試的第一個解決方案是簡單的暴力破解。然而，解決方案的復雜性在于O(2^n)（誰會想到！？）讓我在檢查系統中出現時間限制錯誤。
2) 排序
我開始考慮一個更快的解決方案，可能，比如O(n*logn). 我一開始考慮就n*logn嘗試排序。所以想法如下：
對于每個點，對最接近最遠的其余點進行排序。然后對于每個點，我將遍歷它們并添加到我的矩形，只要它的面積小于或等于s.
但是，在某些情況下，當同一坐標有多個點并且按距離排序沒有考慮到這一點時，這個想法會失敗。
3) 背包
一旦我確定了排序問題，問題就開始看起來像一個背包問題。我們可以通過它們的坐標來聚合這些點，因此具有相同點的點將被分組在一起。對于每個組，我們需要記住該組中有多少點。這將是背包物品的價值。隨著物品的重量，它變得越來越難。我認為背包是一個矩形，所以如果我使用帶有 DP 矩陣的經典解決方案來實作它，那么我可以在每個單元格存盤一個矩形。如果我們選擇它，每組點的權重可以是它將添加到矩形的區域。
但是，這個解決方案對我來說似乎也不正確。原因如下：
- 我們需要為每一點打包一個背包。因為如果我們從某些點開始，我們可能不會到達所有點。所以我們需要檢查所有可能的背包并采取“最重的”。然而，單個背包演算法的復雜性是
O(n*s)，如果我們對每個點都這樣做，它將得到O(n*n*s) = O(n^2*s). 在給定的約束下，這是不可接受的 - 在最壞的情況下，單個背包 DP 矩陣將由
n*s = 3*10^8元素組成。在每個單元格中，我想存盤一個可以表示為 4 個數字的矩形：上界、下界、左界和右界。如果每個邊界都是 uint8，那么矩形本身將占用 4 個位元組。總記憶體將3*10^8*4 = 12*10^8 bytes = 1200 Mb超過記憶體限制。
現在在我看來，背包解決方案也是不正確的。但是，我一直在思考這個問題超過 3 天，找不到另一個解決方案，即使是理論上的
uj5u.com熱心網友回復：
您可以在 O(n 3 ) 時間內輕松完成此操作，考慮到 n <= 300 的約束，這肯定會少于 8 秒。
首先請注意，總會有一個最佳矩形，其頂部、底部和左側邊界都有點。給定任何最佳矩形，如果它的頂部或底部邊框上沒有一個點，那么它的高度可以減小直到它有，而不丟掉任何點。如果它的左邊框上沒有一個點，那么它可以向右移動，直到它有，再次不丟棄任何點。
因此，簡單的解決方案是：
- 按 x 坐標對點進行排序
- 對于每對點 p1、p2，p1.y <= p2.y-1：
- 求上下邊界為 p1 和 p2 的矩形的寬度：w = s/(p2.y - p1.y)。如果太小，將高度調整為 1。
- 使用已排序的點串列，對于 y 在 p1.y 和 p2.y 之間的每個點，如果該點位于左邊緣，則找到可以包含的點數。記住最好的結果。
步驟 2.3 可以使用標準的 2 指標演算法在 O(n) 時間內完成。由于您考慮的每個點都位于前一個點的右側，因此適合的最后一個點也將位于前一個最后一個點的右側。兩個位置都在串列中單調增加。
在 python 中，它看起來像這樣：
def pointsInBestRect(points, area):
points = sorted(points)
bestcount = 0
bestminy = 0
bestmaxy = 0
bestminx = 0
for i in range(len(points)):
p1 = points[i]
for j in range(i, len(points)):
p2 = points[j]
miny = min(p1[1],p2[1])
maxy = max(p1[1],p2[1])
maxy = max(maxy, miny 1)
h = maxy-miny
if h < 1 or h > area:
continue
outpos = 0
count = 0
for pleft in points:
while outpos < len(points) and (points[outpos][0] - pleft[0])*h <= area:
outy = points[outpos][1]
outpos = 1
if outy >= miny and outy <= maxy:
count = 1
if count > bestcount:
bestcount = count
bestminx = pleft[0]
bestminy = miny
bestmaxy = maxy
if pleft[1] >= miny and pleft[1] <= maxy:
count -= 1
besth = bestmaxy - bestminy
return [p for p in points if
p[1] >= bestminy and
p[1] <= bestmaxy and
p[0] >= bestminx and
(p[0]-bestminx) * besth <= area]
print(pointsInBestRect([(1,1),(10,10),(4,5),(5,4)], 1))
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/518005.html
上一篇：如何使用jquery、ajax和html檔案進行無限滾動
下一篇：VBA如何為“每一行”獲取屬性