优化问题算法：拆分倾向于在一起的元素

Question

我无法针对我的问题提出算法。

我有一个

list of lists

，总共有

10

值。列表大小为：

10 >= size >= 1

每个列表代表尽可能保留在一起的值。我需要将它们分成特定数量的块（

numberOfChunks

），以便每个块的大小接近首选大小（

preferredChunkSize = total elements / numberOfChunks

），并且真实的块大小应遵循条件：

preferredChunkSize + maxDeviation >= real chunk size >= preferredChunkSize - maxDeviation

。

函数声明：

function split(buckets: list<list>, numberOfChunks, maxDeviation)

示例0

buckets = [[1, 2, 3], [4], [5], [6, 7, 8, 9, 10]]
chunks = split(buckets, 5, 0)
// acceptable options (max deviation equals 0, so we don't allow the size to be more or less than 2
// [[1,2],[3,4],[5,6],[7,8],[9,10]]

示例1

buckets = [[1, 2, 3], [4], [5], [6, 7, 8, 9, 10]]
chunks = split(buckets, 5, 1)
// acceptable options
// [[1,2,3],[4],[5],[6,7,8],[9,10]]

示例2

buckets = [[1,2,3,4,5,6], [7,8], [9], [10]]
chunks = split(buckets, 2, 1)
// acceptable options
// [[1,2,3,4,5,6],[7,8,9,10]]

示例3

buckets = [[1,2,3,4,5,6], [7,8], [9], [10]]
chunks = split(buckets, 3, 1)
// acceptable options
// [[1,2,3], [4,5,6], [7,8,9,10]]

任何帮助将不胜感激！也许这个或类似的问题已经存在？有谁能说出名字吗

Answer 1

这需要更多的形式主义才能解决。

问题陈述指出块大小必须在给定的范围内。 然而，只有这个硬约束，解决方案就是尽可能均匀地分成块，完全忽略初始块。

还有以下形式的软约束：初始列表中的值最好保持在一起如果可能。这必须以某种方式量化。例如，我们可以引入一个惩罚函数，为每对在同一个列表中但不在答案中的元素添加 1 个单位的惩罚。或者惩罚每对连续的此类元素。

---

当我们有了这样的形式化函数后，我们可以对其进行优化，即尝试找到总惩罚最小的答案。 例如，这看起来可以通过动态编程来完成。 考虑以下形式的状态：

• 我们已经构建了

  k

  块
• 我们总共使用了

  e

  个元素

任务是最小化惩罚函数

f (k, e)

。

显然，基本情况是

f (0, 0) = 0

。

现在，循环遍历下一个块的元素数量，

n

。 我们从状态

(k, e)

转到状态

(k + 1, e + n)

。 添加块的惩罚可以即时计算，因为我们知道，对于所采用的每个

n

元素（它源自哪个列表），其邻居有多少将位于同一块中，以及有多少将转到其他块。

最佳值将是

f (total chunks, total elements)

。 也许有了这个值，我们也会存储获得这个值的方法，然后立即给出答案。