您有一組n給出整數位置的對象。對象的一個組是位於同一位置的一組對象（不一定是該位置的所有對象：在一個位置可能有多個組）。可以將對象移動到左側或右側，目標是移動這些對象以形成組，並以最小距離移動來完成此操作。將一個組劃分爲具有最小移動次數的k組
例如：
我已經b即嘗試使用貪婪的方法（通過計算哪種移動最短），但這種方法無效，因爲每個移動都涉及兩個可以移動的元素。我還沒有能夠制定一個動態編程方法，但我正在研究它。
按照我的理解，問題是：
我們有一行n個點。 我們想把k的位置放在線上。我稱他們爲目的地。 將n個點中的每一個移動到k個目的地中的一個，以使距離之和最小。我把這個總和稱爲總成本。 目的地可以重疊。
一個顯而易見的事實是，對於每個點我們都應該查找左側最近的目的地和右側最近的目的地並選擇最近的目的地。
另一個重要的事實是所有的目的地應該是關鍵點。因爲我們可以將它們在線上向右或向左移動以在不增加總距離的情況下達到某個點。
通過這些事實可以考慮以下DP解決方案：
DP [i] [j]表示需要爲第i點，最低總成本時，我們只能使用Ĵ目的地，並且必須在把目的地第i點。
計算DP [i] [j]在第i個點（我們有i選擇）之前確定目的地，併爲每個選擇（例如第k個點）計算i第 - 個點和新點（第k點）相加。加上DP [k] [j - 1]並找出所有k的最小值。
初始狀態的計算（例如j = 1）和最終答案留作練習！
任務0 - 按照非遞減順序對象的位置
讓我們定義'center'爲對象的位置，在其shifted to.
現在我們有兩點看法;
For N positions the 'center' would be the position which is nearest to the mean of these N positions.例如，讓1,3,6,10爲位置。然後mean = 5.最近的位置是6.因此，這些元素的中心是6.當所有元素需要分組到1組時，這給我們移動成本最小的位置。
設N個位置分組爲K個「最佳」組。 When N+1 th object is added，那麼它會擾亂僅第K個組，即，first K-1 groups will remain unchanged.
從這些觀察，我們建立了一個動態規劃方法。
Let Cost[i][k] and Center[i][k] be two 2D arrays.
Cost[i][k] = minimum cost when first 'i' objects are partitioned into 'k' groups
Center[i][k] stores the center of the 'i-th' object when Cost[i][k] is computed.
Let {L} be the elements from i-L,i-L+1,..i-1 which have the same center.
(Center[i-L][k] = Center[i-L+1][k] = ... = Center[i-1][k])
這些都是需要在計算被考慮第i個元素（從觀察2）現在
Cost[i][k] will be
min(Cost[i-1][k-1] , Cost[i-L-1][k-1] + computecost(i-L, i-L+1, ... ,i))
Update Center[i-L ... i][k]
computecost唯一對象（）可以通過找到中心而輕鬆找到（來自觀察1）
時間複雜度：
Sorting O(NlogN)
Total Cost Computation Matrix = Total elements * Computecost = O(NK * N)
Total = O(NlogN + N*NK) = O(N*NK)
觀察1是錯誤的。說你的分數是1,2,3,4,10。平均數是4，所以你會選擇4.這個成本是3 + 2 + 1 + 6 = 12，但是如果你選擇3，那麼成本是2 + 1 + 1 + 7 = 11。事實上，如果所有的點都移動到一個點上，那麼它應該是一個在點的兩側具有相同點數的點。我在答案中進一步解釋了這一點。 – Dave
讓我們看看k = 1。
對於k = 1和n奇數，所有點應該移動到中心點。對於k = 1和n偶數，所有點應移動到中心點或它們之間的任何點。我所說的「中心」是指任何一方的點數，即中位數。
你可以看到這一點，因爲如果你選擇一個目標點x，右邊的點多於它的左邊，那麼x右邊的新目標1會導致成本降低（除非有一個點更多指向右側而不是左側，目標點是一個點，在這種情況下，n是偶數，目標位於兩個中心點之間/之間）。
如果你的積分已經排序，這是一個O（1）操作。如果不是，我相信它是O（n）（通過訂單統計算法）。
找到所有點都移動到的點後，找到成本就是O（n）。
因此，無論點是否排序，這是O（n）。
此問題是k-medians problem的一維實例，可以說明如下。給定一組點x_1 ... x_n，將這些點分爲k個集合S_1 ... S_k，並選擇k個位置y_1 ... y_k，使得| x_i - y_f（i）|的所有x_i的總和最小。 ，其中y_f（i）是x_i被分配到的集合的對應位置。
由於中位數爲population minimizer for absolute distance (i.e. L_1 norm)，因此每個位置y_j將是相應集合S_j中的元素x的中值（因此稱爲k-中值）。既然你正在查看整數值，那麼有一個技術含義，如果S_j包含偶數個元素，中位數可能不是整數，但在這種情況下，選擇高於或低於中位數的下一個整數將給出相同的總和絕對距離。
解決k-中位數（以及相關和更常見的k-means問題）的標準啓發式算法是迭代的，但這並不能保證產生最佳或甚至是好的解決方案。解一般度量空間的k-中值問題是NP難題，爲k-中值尋找有效的近似值是一個開放的研究問題。例如，谷歌搜索「k-medians近似」會導致大量論文給出近似方案。 http://www.cis.upenn.edu/~sudipto/mypapers/kmedian_jcss.pdf http://graphics.stanford.edu/courses/cs468-06-winter/Papers/arr-clustering.pdf
在一個層面的事情變得更容易，您可以使用動態規劃方法。在this paper中描述了針對相關一維k均值問題的DP解決方案，並且R中的源代碼可用於here。有關詳細信息，請參閱文件，但這個想法基本上與@SajalJain提出的一樣，並且可以很容易地適用於解決k中值問題而不是k-均值。對於j < = k和m < = n設D（j，m）表示對x_1 ... x_m的最優j-中值解的代價，其中x_i假定爲排序順序。我們有復發
D(j,m) = min (D(j-1,q) + Cost(x_{q+1},...,x_m)
其中q範圍從j-1到m-1和Cost是等於從值絕對距離的總和。通過Cost的簡單O（n）實現，這將產生一個O（n^3k）DP解決方案來解決整個問題。然而，這可以被改進，以O（N^2K）由於其成本可在恆定的時間，每次使用的事實更新，而不是從頭開始計算，即，對於一個排序序列：
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_1...x_h)-x_1 if h is odd
Cost(x_1,...,x_h) = Cost(x_2,...,x_h) + median(x_2...x_h)-x_1 if h is even
查看文章瞭解更多詳情。除了成本函數的更新不同之外，對於k-中值和k-均值的實現將是相同的。 http://journal.r-project.org/archive/2011-2/RJournal_2011-2_Wang+Song.pdf
是不是：Set :: [1,2,5,9] --->分成2組::: Min Moves = 1 + 3 = 4？ –
不是，在位置2會有2個元素.....所以Moves = 1 + 3 * 2 = 7 – Leopard
爲什麼你不能移動5和1到2？ –