algorithm - 将一组数字划分为 k 个子集，使值均匀分布

Question

可能重复：
相等 k 个子集算法

假设我有一组数字，我想将这些数字分成 k 个子集，以便这些数字均匀分布。通过均匀分布，我的意思是子集中的值的总和最接近其他子集的其他总和。我们可以对这个问题实施 DP 解决方案吗？

请建议！

Answer 1

我所能提供的只是我最好的尝试，这里是：

在我看来，如果 m 是你的集合的大小，那么 m/k = n; 这是每个集合中的元素数。

现在我假设您正在使用整数，假设我们是一个集合，s：

s ={1,2,3,4,5,6,7,8}

现在这是一个简单的想法，如果你设置排序，那么位置的总和
-Sum(0 和 last-0) = Sum(1,Last-1) = Sum(2,last-2) = Sum(3,last -3)...等等。

变量将是：

• 米 = 8
• k = 2（仅作为示例）
• n = 4

所以我们想要 4 组： s1 = 1,8 = Sum 是 9 s2 = 2,7 = Sum 是 9 s3 = 3,6 = Sum 是 9 s4 = 4,5 = Sum 是 9

现在，如果集合大小是奇数和/或 k 是奇数，当然会有一些棘手的问题，但是可以使用特殊情况来处理这些问题——实现最适合您特定目的的情况。

希望这能给你一个正确的推动力，或者几乎任何方向。