自定义分区问题

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

给定一个集合 S，其中有 k 个元素。

现在我们必须将集合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 中的数字，但不会增加两个子集之间的绝对差异。交换两个数字。重复。并非所有子集对都具有可交换的数字。每次交换都会使子集保持相同的大小。

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

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