php算法将一组数据分成不超过四个的组

Question

我目前遇到的问题是我有一个大约有 1000 个条目的数据集。

每个条目都有两个相关的特征:

• 权重( float )
• origin(字符串/另一个实体)

我必须将这些条目分类为最大组。四个条目。不过，组可以包含较少的条目。

• 四人一组:非常好
• 三个条目一组:好
• 两个条目一组:不太好
• 一组一个条目:非常糟糕(但如果无法避免，则可能)

现在，这些条目被分类到组中的方式取决于它们的以下特征:

• 最大值组内权重的增量可以是10%。
• 每个组中的 origin 应该有尽可能多的不同值。有一个重复项并没有那么糟糕，但是应该避免具有相同 origin 的三个或更多条目。

在数据集中，weight 的范围大约在 20.0 到 120.0 之间。origin 大约有 50 个不同的可能值。

我必须在 php 中实现它，但不需要用 php 实现来回答。算法本身就足够了。

我已经尝试根据它们的 weight 对所有值进行排序，然后简单地每隔四个条目将它们拆分一次。但是我得到的组很难根据 origin 值重新排列。我想我可以通过一个令人讨厌的实现以某种方式完成这项工作，但我希望有一个非常优雅的算法可以做到这一点。

提前致谢!

Answer 1

这是一个可能会产生好的结果的贪心算法:

Sort entried by weight
groups = []
used = array of length len(entries) initialized in false    
For i = 0 to len(entries):
    if (used[i] == false):
        group = [entries[i]]
        j = i + 1
        while(j < len(entries) and delta(group[0], entries[j]) < 10 and len(group) < 4):
           if used[j] == false and entries[j].origin != all the origins in group:
               group.add(entries[j])
               used[j] = true
           j = j + 1
        if (len(group) < 4):
            //decide if you prefer a small group or a bigger group with repeated origins
        groups.add(group)