请问有人可以指导我如何解决这个问题。
我们有一个包含k个元素的集合S。
现在我们需要把集合S分成x个子集,使得每个子集中元素数量的差异不超过1,并且每个子集的元素之和尽可能接近。
例1: {10, 20, 90, 200, 100} 需要分成2个子集
解:{10,200}{20,90,100}
每个子集的元素之和为210和210
例2: {1, 1, 2, 1, 1, 1, 1, 1, 1, 6}
解:{1,1,1,1,6}{1,2,1,1,1}
每个子集的元素之和为10和6。
请问有人可以指导我如何解决这个问题。
我们有一个包含k个元素的集合S。
现在我们需要把集合S分成x个子集,使得每个子集中元素数量的差异不超过1,并且每个子集的元素之和尽可能接近。
例1: {10, 20, 90, 200, 100} 需要分成2个子集
解:{10,200}{20,90,100}
每个子集的元素之和为210和210
例2: {1, 1, 2, 1, 1, 1, 1, 1, 1, 6}
解:{1,1,1,1,6}{1,2,1,1,1}
每个子集的元素之和为10和6。
我看到了一个可能的解决方案,分为两个阶段。
第一阶段
首先选择子集数量N。 如果可能的话,对原始集合S进行排序。 将S中最大的N个数按顺序分配到1到N的子集中。 将S中接下来N个最大的数字按相反的顺序分配到子集中,从N到1。 重复此过程直到所有数字都被分配。
如果无法对S进行排序,则将S中的每个数字分配到条目最少且总和最小的子集(或其中一个子集)中。
现在你应该有N个大小相差不超过1且总和非常接近的子集。
第二阶段
现在尝试改进你已经得到的近似解决方案。 选择总和最大的子集L和总和最小的子集M。选择L中比M中的某个数字小但不会增加两个子集之间绝对差异太多的数字。交换这两个数字。重复此过程。并非所有子集对都有可交换的数字。每次交换保持子集的大小不变。
如果你有很多时间,可以进行彻底的搜索;如果没有,那么只需尝试解决一些明显的情况。我建议如果没有减少差异就不要交换数字;否则可能会陷入无限循环。
一旦某些子集中至少有两个成员,你可以交替进行这两个阶段。
这个问题没有简单的算法。
请查看划分问题,也被称为最简单的困难问题,它可以解决两个集合的情况。这个问题是NP-Complete,你应该能够在网上找到所有解决它的算法。
我知道你的问题有点不同,因为你可以选择集合的数量,但你可以从之前问题的解决方案中获得启示。
例如:
你可以将其转化为一系列线性规划问题,让k成为你集合中元素的数量。
{a1 ... ak} is your set
For i = 2 to k:
try to solve the following program:
xjl = 1 if element j of set is in set number l (l <= i) and 0 otherwise
minimise max(Abs(sum(apxpn) -sum(apxpm)) for all m,n) // you minimise the max of the difference between 2 sets.
s.t
sum(xpn) on n = 1
(sum(xkn) on k)-(sum(xkm) on k) <= 1 for all m n // the number of element in 2 list are different at most of one element.
xpn in {0,1}
if you find a min less than one then stop
otherwise continue
end for
编辑
我看到了你的评论,我误解了子集大小的限制(我以为是两个集合之间的差异)。 我现在没时间更新,等我有时间了再做。 抱歉。
编辑2
我编辑了线性规划,并且它应该做到了它被要求做的事情。我只是添加了一个约束条件。
希望这次问题已经被完全理解,尽管这个解决方案可能不是最优的。
我不是科学家,所以我会尝试两种方法:
在排序项目后,从“两端”开始移动首尾到实际集合,然后移动到下一个集合并循环;
然后:
k
和x
可以有多大? - IVlad