自定义分区问题

Question

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

给定一个集合 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 。

Answer 1

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

第一阶段

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

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

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

第二阶段

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

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

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

Answer 2

对于这个问题没有简单的算法。

查看分区问题，也称为最简单的难题，解决了 2 组问题。这个问题是 NP 完全问题，你应该能够在网上找到解决它的所有算法

我知道你的问题有点不同，因为你可以选择组数，但你可以从之前的解决方案中启发自己一。

例如：

您可以将其转换为一系列线性程序，令 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个集合之间的差异）
我没有时间更新，等我有时间了再更新。
sryy

---

编辑 2

我编辑了线性程序，它应该执行要求执行的操作。我刚刚添加了一个约束。

希望这次问题得到充分理解，即使这个解决方案可能不是最佳的

Answer 3

我不是科学家，所以我会尝试两种方法：

对项目进行排序后，然后从两个“末端”开始，将第一个和最后一个移动到实际的集合，然后转移到下一个集合，循环；

然后：

1. 检查各组总和的差异，并重新排列项目（如果有帮助）。
2. 对结果集进行适当编码并尝试遗传算法。