n個村莊排在一條直線上，位置分別為c1, c2,...,cn 且c1=0<c2<...<cn。為方便大家出行，準備在其中的m個村莊設定公交車站，而每個村莊的人都會利用最近的車站坐車。求車站的最佳設定位置，使各村莊到最近車站的距離之和最小。
（一種思路）
1. 如果村莊i與村莊j (i<j) 設有車站，而其間的村莊沒有車站。則村莊i+1,i+2,..,j-1只能選擇i和j中較近的車站坐車。
設w(i,j)為它們到最近車站的距離之和，顯然w(i,j)=0, if j-i=1.
2. 設S(i,k) 為前i個村莊中設定k個車站且第k 個車站設定第i個村莊的情況下，前i個村莊到最近車站距離之和的最小值。
S(i,k) = min {S(i-1,k-1)+w(i-1,i), S(i-2,k-1)+w(i-2,i),...,S(k-1,k-1)+w(k-1,i)} if (i>k>1)
S(i,k)=0 if (i<=k)
S(i,1) = ?
3. 追加第n+1個村莊且cn+1>2cn。則整個問題的最優解為S(n+1,m+1)。
（要求）
根據上述思路，寫出完整的遞推方程式。
并求解： {0,3,7,9,13,23,28,38,40,56,62,65}中設定5座車站的最佳結果。
分析時間復雜度，思考如何優化w(i,j)的計算。
uj5u.com熱心網友回復：
直接上K-means演算法吧轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/94553.html
標籤：語言基礎/算法/系統設計
下一篇：求助一個sql優化