如何將數組分成N個最小和子集？

如何將整數數組劃分爲N個子集，使得這些子集的總和最小？例如，該數組由11個元素組成，我需要6個子集。如何將數組分成N個最小和子集？

{2,1,1,3,4,4,3,2,1,2,3}

子集：{2,1,1,3}, {4}, {4,3}, {3,2}, {1,2}, {3}最小總和= 7。

備選答案：{2,1,1} {3,4} {4} {3,2} {1,2} {3}最小總和= 7。

注意：數字出現在原始集合中的順序必須在分區時保留。

來源

2016-05-23 Arijit Pramanick

我不明白你的意思最小的總和。在第一行中有一組總和爲3. – Carlos

將數組劃分爲N個子集，使得每個子集的總和小於或等於每個子集可能的最小總和。 –

嘗試製作6個分區，其中每個分區的總和將小於7. –

一種可能的方法是二進制搜索答案。

我們需要一個程序來檢查我們是否可以僅使用等於或低於參數S的總和來劃分集合。我們稱之爲onlySumsBelow(S)。

我們可以使用一個貪婪的解決方案來實現onlySumsBelow(S)。總是在每個子集中添加儘可能多的元素，並在達到大於S的總和之前停止（我在這裏假設我們沒有負面元素，這可能會使討論複雜化）。如果我們無法使用允許的子集數達到序列末尾，那麼總和無效（它太小）。

function onlySumsBelow(S) { 
    partitionsUsed = 1; 
    currentSum = 0; 

    for each value in sequence { 
     if (value > S) return false; 

     if (currentSum + value > S) { 
      // start a new partition 
      currentSum = value; 
      partitionsUsed++; 
     } else { 
      currentSum += value; 
     } 
    } 

    return partitionsUsed <= N; 
}

一旦我們有了onlySumsBelow(S)過程中，我們可以爲答案二進制搜索，開始以一定間隔，在左端具有確保搜索的答案是不低於一個值（例如 0）和在右端有足夠大的數字以確保搜索到的答案不在上面（，例如是序列中所有數字的總和）。

如果效率不是問題，而不是二元搜索，您可以簡單地嘗試多個候選答案，從足夠小的值開始，例如所有數字之和除以N，然後增加1，直到達到一個好的解決方案。

備註：在問題末尾沒有註釋（這限制了我們考慮在輸入中出現在相鄰位置的數字的子集），問題是NP完全的，因爲它是Partition problem，它只使用兩組。

來源

2016-05-23 14:23:05 qwertyman

如何通過過程onlySumsBelow（S）添加數字時如何保持分區數量？ –

我爲onlySumsBelow（S）過程添加了一些僞代碼。另外，提到如果效率不是問題，您可以避免二分查找並使用線性搜索。 – qwertyman

如何將數組分成N個最小和子集？

回答

相關問題