需要主意來解決這個算法的難題

Question

我在過去遇到過這樣的一些類似的問題，我還沒有好的想法如何解決這個問題。問題如下：

給出一個大小爲n的正整數數組< = 1000和k < = n這是您必須將數組拆分成的連續子數的數量。您必須輸出最小值m，其中m = max {s [1]，...，s [k]}，s [i]是第i個子陣列的總和。示例：

Input:       Output: 
5 3 >> n = 5 k = 3    3 
2 1 1 2 3 

將數組拆分爲2 + 1 | 1 + 2 | 3將最小化米。

我的蠻力想法是讓第一個子陣列在位置i結束（對於所有可能的i），然後嘗試以儘可能最好的方式將k-1子陣列中的其餘數組拆分。但是，這是指數解決方案，將永遠不會工作。

所以我正在尋找好的想法來解決它。如果你有一個請告訴我。

感謝您的幫助。

Answer 1

你可以使用動態規劃來解決這個問題，但實際上你可以用貪婪的二叉搜索來解決答案。該算法的複雜性爲O(n log d)，其中d是輸出答案。 （上限將是數組中所有元素的總和。）（或O(n d)中輸出位的大小）

這個想法是在你的m將會是二進制搜索 - 然後貪婪地前進在陣列上，將當前元素添加到分區，除非添加當前元素將其推送到當前的m--在這種情況下，您將啓動一個新的分區。目前的m是成功的（因此調整你的上限），如果使用的分區數小於或等於你給定的輸入k。否則，你使用了太多分區，並在m上提高下限。

一些僞代碼：

// binary search 
binary_search (array, N, k) { 
    lower = max(array), upper = sum(array) 

    while lower < upper { 
     mid = (lower + upper)/2 

     // if the greedy is good 
     if partitions(array, mid) <= k 
      upper = mid 
     else 
      lower = mid 
    } 
} 

partitions(array, m) { 
    count = 0 
    running_sum = 0 

    for x in array { 
     if running_sum + x > m 
      running_sum = 0 
      count++ 
     running_sum += x 
    } 
    if running_sum > 0 
     count++ 
    return count 
} 

這應該是比較容易拿出概念。另外請注意，由於分區函數的單調性質，實際上你可以跳過二進制搜索，做一個線性搜索，如果你是確保輸出d不是太大：

for i = 0 to infinity 
    if partitions(array, i) <= k 
     return i 

Answer 2

動態編程。製造陣列

int best[k+1][n+1]; 

其中best[i][j]是可以實現分裂數組的第一個元素j詮釋i子陣最好的。 best[1][j]只是第一個j數組元素的總和。具有行i，則計算行i+1如下：

for(j = i+1; j <= n; ++j){ 
    temp = min(best[i][i], arraysum[i+1 .. j]); 
    for(h = i+1; h < j; ++h){ 
     if (min(best[i][h], arraysum[h+1 .. j]) < temp){ 
      temp = min(best[i][h], arraysum[h+1 .. j]); 
     } 
    } 
    best[i+1][j] = temp; 
} 

best[m][n]將包含解決方案。算法是O（n^2 * k），可能更好些。

編輯：ChingPing，toto2，火星咖啡和rds（按照我目前看到的頁面顯示的順序）的組合。

設置A = ceiling(sum/k)。這是最小值的下限。要找到最小值的上限，請使用上述任何方法創建一個好的分區，移動邊界，直到找不到任何仍然會減少最大子數目的簡單移動。這給了你一個上限B，並不比下限大（如果它更大，我認爲你可以通過移動邊界找到一個簡單的改進）。 現在繼續使用ChingPing算法，已知上限減少了可能分支的數量。最後一個階段是O（（B-A）* n），發現B未知，但我猜測比O（n^2）更好。

Answer 3

我有一個蘇茨基分支定界算法（請不要downvote我）

首先採取陣列和dvide通過k的總和，爲你解答，即平均A.同樣，讓你綁定的最好的情況下，我們將保持迄今爲止對於任何分支GO（全局最優）所見的最佳解決方案。讓我們考慮在某個數組元素後面放置一個分區（邏輯）作爲分區單元，並且我們必須放入k-1個分區。現在我們將這樣貪婪地放置分區，

遍歷數組元素總結它們，直到您看到在下一個位置我們將超過A，現在創建兩個分支之一，您將分隔符放在此位置和其他位置你放在下一個位置，做這個遞歸併設置GO = min（GO，回答分支）。 如果在任何分支的任何一點，我們都有一個大於GO的分區，否則位置的數量少於我們綁定的分區。最後，當你回答時，你應該有GO。

編輯： 作爲建議由丹尼爾，我們可以修改分配器放置策略一點，直到你到達的元素爲A或左其餘職位的總和將其值應小於分隔。

Answer 4

這只是一個想法的草圖......我不確定它的工作原理，但它很容易（也可能很快）。

你開始說分離均勻分佈（它實際上並不關心你如何開始）。

做出每個子陣列的總和。
找到總和最大的子數組。
查看左右相鄰的子陣列，如果左側的子陣列的總和低於右側的子集（反之亦然），則將左側的分隔向左移動1。
重做當前最大總和的子數組。

你會遇到一些情況，你會繼續反彈相同的兩個職位之間的分隔，這可能意味着你有解決方案。

編輯：請參閱@rds的評論。您必須更加努力地思考解決方案和最終條件。

Answer 5

如果你的數組有隨機數，你可以希望每個子數組有n/k的分區是一個很好的起點。

從那裏

1. 評估這個候選解決方案，通過計算的金額
2. 商店這個候選解決方案。例如具有：
   • 每個子陣列的索引的陣列
   • 求和子陣列的對應的最大
3. 降低最大子陣列的大小：創建兩個新的候選：一個子數組從索引+ 1開始;一個以子陣列結尾於index-1
4. 評估新的候選人。
   • 如果它們的最大較高，丟棄
   • 如果它們的最大較低，迭代2，除非該候選已經評估，在這種情況下，它是解決方案。

Answer 6

我的想法，不幸的是不起作用：

1. 斯普利特陣列的N子陣列
2. 找到兩個相鄰子陣列，其總和是至少
3. 合併發現子陣在步驟2中形成新的連續子陣列
4. 如果子陣列的總數大於k，則從步驟2開始迭代，否則結束。