演算法問題

[sorryChen (陳揚和)]

(不好意思post再這裡,若應該post再其他版上還請版友告知見諒)
給定n個數選k個數使其中選中的數之間的最短距離最大化
就比如說一個街道上要從n個點中選k個點放垃圾桶
要使最近的兩個垃圾桶距離最大化


一開始覺得這個是個簡單又典型的問題 但想了兩天除了一個O(n^3k)的DP方法
並沒有什麼好的解法... 其他一些想法是..頭尾都一定會選
如果可以隨便放的話L/(k-1)的間隔距離放最好, L 為街道總長
所以若第二個個點大過L/(k-1)則就一定會要選 因為選的時候不會造成瓶頸
但若小於則不一定是最好的 因為可能會造成瓶頸...

不知道版友們能不能指導一下


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.151.230.57
※ 編輯: sorryChen       來自: 207.151.230.57       (04/11 10:58)
推 march20:四方是指 n^4?
→ sorryChen:對阿 n^3 * k
※ 編輯: sorryChen       來自: 207.151.230.57       (04/11 13:02)
→ askker:給定的n個數字間有規律嗎?
推 yoco315:幫推，想不出來 -,-
推 march20:看來是個 n*n*k 的表
推 march20:好像夠好了 @@
推 march20:咦, 似乎可以少一個 n. 考慮這樣的表
推 march20:T[i,j]=起點為 p0, 終點為 pi 總共選j點
推 march20:其中最大的最小距離?
推 march20:T[i,j]=max(1<x<i;min(T[x,j-1],D(x,i)))
推 march20:            =
推 march20:不過"起點一定會選"看起來是個錯的假設@@
推 march20:(又想了一下, 拿掉 p0 好像不會怎樣)
推 march20:(所以 k*n^2 應該是可以達成的)
推 stimim:use binary search might have a O(n lg L)
→ stimim:algorithm,sorry I can't type chinese now
→ stimim:where L is the dist. form start to end
→ stimim:                      ^^^^  from
→ sorryChen:非常感謝前輩的回答 我轉錄了同學的解答