请问有人可以指导我如何解决这个问题。
我们有一个包含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。
3个回答
2
我看到了一个可能的解决方案，分为两个阶段。
第一阶段
首先选择子集数量N。 如果可能的话，对原始集合S进行排序。 将S中最大的N个数按顺序分配到1到N的子集中。 将S中接下来N个最大的数字按相反的顺序分配到子集中，从N到1。 重复此过程直到所有数字都被分配。
如果无法对S进行排序，则将S中的每个数字分配到条目最少且总和最小的子集（或其中一个子集）中。
现在你应该有N个大小相差不超过1且总和非常接近的子集。
第二阶段
现在尝试改进你已经得到的近似解决方案。 选择总和最大的子集L和总和最小的子集M。选择L中比M中的某个数字小但不会增加两个子集之间绝对差异太多的数字。交换这两个数字。重复此过程。并非所有子集对都有可交换的数字。每次交换保持子集的大小不变。
如果你有很多时间，可以进行彻底的搜索；如果没有，那么只需尝试解决一些明显的情况。我建议如果没有减少差异就不要交换数字；否则可能会陷入无限循环。
一旦某些子集中至少有两个成员，你可以交替进行这两个阶段。
- rossum
1
这个问题没有简单的算法。
请查看划分问题，也被称为最简单的困难问题，它可以解决两个集合的情况。这个问题是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
希望我的注释清晰明了。
这个程序的复杂度是指数级的，如果你找到了一种多项式解决方法，那么你将会证明 P=NP，所以我认为你做不到更好。
编辑
我看到了你的评论，我误解了子集大小的限制（我以为是两个集合之间的差异）。 我现在没时间更新，等我有时间了再做。 抱歉。
编辑2
我编辑了线性规划，并且它应该做到了它被要求做的事情。我只是添加了一个约束条件。
希望这次问题已经被完全理解，尽管这个解决方案可能不是最优的。
- Ricky Bobby
3
这有些不同：在这种情况下，子集的大小只能相差最多1。我认为当前的答案形式并不是很有帮助。维基百科文章确实提到了这个条件，但没有给出如何处理它的指示。此外，仅仅拥有超过两个子集就会显著改变游戏规则。 - IVlad
好的，我误读了文本，我想你可以轻松地修改我的解决方案以得到一个可行的解决方案。只需更改线性规划的约束条件即可。我稍后会尝试更新它。 - Ricky Bobby
@IVlad，我编辑了程序，使其符合所有约束条件。感谢您的评论，我一开始误读了问题。 - Ricky Bobby
0
我不是科学家，所以我会尝试两种方法：
在排序项目后，从“两端”开始移动首尾到实际集合，然后移动到下一个集合并循环；
然后：
- 检查集合之和的差异，并在需要时重新排列项目。
- 适当编写结果集并尝试遗传算法。
- Ondra Žižka
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
k和x可以有多大？ - IVlad