5

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

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

4

3 回答 3

2

我在两个阶段看到了一个可能的解决方案。

第一阶段

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

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

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

第二阶段

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

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

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

于 2011-07-21T20:59:16.477 回答
1

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

查看分区问题，也称为最简单的难题，解决了 2 组问题。这个问题是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 套之间的差异）我没有时间更新它我有时间会做。sryy

编辑 2

我编辑了线性程序，它应该做它被要求做的事情。我刚刚添加了一个约束。

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

于 2011-07-21T17:12:13.987 回答
0

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

对项目进行排序后，从“两端”依次移动到实际集合，然后转移到下一个集合，循环；

然后：

  1. 检查集合总和的差异，如果有帮助的话，对项目进行洗牌。
  2. 对结果集进行适当编码并尝试遗传算法。
于 2011-07-21T17:29:40.020 回答