如何将一个集合划分为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）的第二个分区。