PTT數位生活區 / Programming

演算法問題

看板Programming作者 (陳揚和)時間16年前 (2010/04/11 10:57), 編輯推噓13(13推 0噓 6→)
留言19則, 5人參與, 最新討論串1/2 (看更多)
(不好意思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)
推
04/11 12:31, , 1F
四方是指 n^4?
04/11 12:31, 1F
→
04/11 12:59, , 2F
對阿 n^3 * k
04/11 12:59, 2F
※ 編輯: sorryChen 來自: 207.151.230.57 (04/11 13:02)
→
04/11 13:04, , 3F
給定的n個數字間有規律嗎?
04/11 13:04, 3F
推
04/11 13:27, , 4F
幫推，想不出來 -,-
04/11 13:27, 4F
推
04/11 16:44, , 5F
看來是個 n*n*k 的表
04/11 16:44, 5F
推
04/11 16:45, , 6F
好像夠好了 @@
04/11 16:45, 6F
推
04/11 16:53, , 7F
咦, 似乎可以少一個 n. 考慮這樣的表
04/11 16:53, 7F
推
04/11 16:55, , 8F
T[i,j]=起點為 p0, 終點為 pi 總共選j點
04/11 16:55, 8F
推
04/11 16:56, , 9F
其中最大的最小距離?
04/11 16:56, 9F
推
04/11 17:00, , 10F
T[i,j]=max(1<x<i;min(T[x,j-1],D(x,i)))
04/11 17:00, 10F
推
04/11 17:03, , 11F
=
04/11 17:03, 11F
推
04/11 17:05, , 12F
不過"起點一定會選"看起來是個錯的假設@@
04/11 17:05, 12F
推
04/11 17:08, , 13F
(又想了一下, 拿掉 p0 好像不會怎樣)
04/11 17:08, 13F
推
04/11 17:11, , 14F
(所以 k*n^2 應該是可以達成的)
04/11 17:11, 14F
推
04/11 20:28, , 15F
use binary search might have a O(n lg L)
04/11 20:28, 15F
→
04/11 20:29, , 16F
algorithm,sorry I can't type chinese now
04/11 20:29, 16F
→
04/11 20:29, , 17F
where L is the dist. form start to end
04/11 20:29, 17F
→
04/11 20:31, , 18F
^^^^ from
04/11 20:31, 18F
→
04/13 14:19, , 19F
非常感謝前輩的回答 我轉錄了同學的解答
04/13 14:19, 19F
‣ 更多 sorryChen 的文章
文章代碼(AID): #1BmJgoKE (Programming)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
排序： 最新先 | 最舊先 | 留言數
13
19
演算法問題
sorryChen
16年前, 04/11
在新視窗開啟完整討論串 (共2篇)
Programming 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 sorryChen 的文章
文章代碼(AID): #1BmJgoKE (Programming)