如何將一個集合劃分爲K個子集，這樣子集中元素的總和最小？

Question

我正在學習DP，並且在閱讀平衡分區算法時遇到了這個問題。在這個算法中，我們可以將列表分成兩個列表，這些列表的元素總和相等。但是如果我需要K列表並且我需要他們有一個最小的總和呢？我想修改平衡分區算法來解決這個問題，但我實際上沒有辦法做到這一點。設S爲{1,1，5}，K = 2的最優解爲{1,1}，{5}。

任何提示？ 在此先感謝。

Answer 1

一個簡單的算法將是：

sort S in descending order 
for each element in S: 
    put it into the partition with the smallest sum 

這將使5到第一分區和所述1 s轉換在你的例子（K = 2）的第二個分區。