自定义分区问题

Question

有人可以指导我如何解决这个问题.

我们给出一个具有k个元素的集合S.

现在我们必须将集合S划分为x个子集,使得每个子集中元素数量的差异不大于1,并且每个子集的总和应尽可能彼此接近.

示例1:{10,20,90,200,100}必须分为2个子集

解决方案:{10200} {} 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.

Answer 1

我认为可能的解决方案分两个阶段。

第一阶段

首先选择子集的数量 N。如果可能，对原始集 S 进行排序。将S中最大的N个数按顺序分配到子集1到N中。以相反的顺序从 N 到 1 分配子集中接下来的 N 个最大数字。重复直到所有数字都分配完毕。

如果无法对 S 进行排序，则将 S 中的每个数字分配到条目最少且总数最小的子集（或子集之一）中。

您现在应该有 N 个子集，所有子集的大小都在 1 以内，并且总数非常大致相似。

第二阶段

现在尝试完善您的近似解决方案。选择最大的总子集 L 和最小的总子集 M。选择 L 中的一个数字，该数字小于 M 中的数字，但不会增加两个子集之间的绝对差异。交换两个数字。重复。并非所有子集对都具有可交换的数字。每次交换都会使子集保持相同的大小。

如果你有很多时间，你可以彻底搜索；如果没有，那么就尝试挑选一些明显的案例。我想说的是，如果差异没有减少，就不要交换数字；否则你可能会陷入无限循环。

一旦某些子集中至少有两个成员，您就可以交错各个阶段。