algorithm - 将有序数据集分组为最少数量的簇

Question

我有一个有序的加权项目列表，每个项目的权重小于或等于 N。我需要将其转换为集群列表。每个簇应该跨越几个连续的项目，并且一个簇的总权重必须小于或等于 N。

有没有一种算法可以做到这一点，同时最大限度地减少簇的总数并保持它们的权重尽可能均匀？

例如列表 [(a,5),(b,1),(c,2),(d,5)], N=6 应转换为 [([a],5),([b,c], 3),([d],5)]

Answer 1

由于数据集是有序的，一种可能的方法是为每个可能的集群分配一个“坏度”分数，并使用让人联想到 Knuth 的自动换行 (http://en.wikipedia.org/wiki/Word_wrap) 的动态程序来最小化坏度分数的总和。 badness 函数可让您探索最小化聚类数量(更大的常数项)和平衡它们(偏离平均项目数的更大惩罚)之间的权衡。