限制条件下的筛选列表

Question

输入是按分数排序的列表 ，item如下所示：

class Item {
    double score;
    String category; 
    String author;    
    String poi;   
}

现在我需要在以下限制下从数组中选择10个得分最高的元素：

• 它们应该具有不同的POI
• 它们应该有不同的作者
• 同一类别中最多有3个项目。并且来自同一类别的任何子序列的长度不应大于2。

• 如果已经有一个选定的元素具有此POI，那么新元素将被丢弃。
• 如果已经有一个选定的元素具有这个作者，那么新元素将被丢弃。
• 如果已经有三个选定元素具有此类别，那么新元素将被丢弃。
• 如果在选定的尾部已经有两个元素具有此类别，那么新元素将被丢弃。

它在输入较大时起作用，但在输入相对较小时就不起作用了。例如，当输入为

1. 项目1（A类，作者1)
2. 项目2（A类，作者2)
3. 项目3（A类，作者3)
4. 项目4（B类，作者2)
5. 项目5（C类，作者5)
6. 项目6（D类，作者6)
7. 项目7（E类，作者7)
8. 项目8（F类，作者8)
9. 项目9（G类，作者9)
10. 项目10（类别H，作者10)
11. 项目11（第一类，作者11)

null

我想我的解决方案只是方向不对。所以我在寻找其他解决方案来处理这个问题。任何解决方案产生所需的输出都是赞赏的。

Answer 1

您使用的原始算法总是倾向于最小化结果的数量，因为在任何相互排斥的项目之间的选择中，得分最高的项目获胜。这样，算法就像筛子一样操作，消除了许多得分较低的项目。

为了支持从长度为Y（在您的示例中为11）的原始项集中选择至少大小为X（在本例中为10）的项集，您将需要收集决策集列表，而不是仅通过分数来消除项。决策集（m,n）是一个由m个项目组成的集合，您必须从中选择保留n个项目并消除其余项目。由于系统中的大多数规则都是属性x的单个项，所以列表中的大多数决策集将被设置为(m，1)-从m项中选择1项，删除其余项。

对完整项集的第一次传递将填充决策集列表，第二次传递将遍历该列表，并从每个决策集中选择要从原始集中删除的项。一旦做出了决策，并且从原始集合中消除了项/s，决策集就从列表中删除（解析）。一旦清除了决策集列表，您的原始集就是合法的。

目标是使决策集列表在最多Y-X消除中被清除。由于一个项目可以出现在多个决策集中，您也可以为每个项目添加一个“生存分数”。生存分数表明，如果该项目被保留，该项目将不得不被消除的最大数量。它是通过遍历每个决策集(m，n)并向包含m-n的每个项目添加其累积得分来计算的。

让我们看看您的示例，并构建它的决策集：

• 项目1（A类，作者1)
• 项目2（A类，作者2)
• 项目3（A类，作者3)
• 项目4（B类，作者2)
• 项目5（C类，作者5)
• 项目6（D类，作者6)
• 项目7（E类，作者7)
• 项目8（F类，作者8)
• 项目9（G类，作者9)
• 项目10（类别H，作者10)
• 项目11（第一类，作者11)

null

我们的目标是在最多1个消除中解决决策集列表。你可以看到所有的物品都是生存分数为1（这意味着保留它们将导致最多1个其他物品被消除），除了第二个物品，它的生存分数为2（保留它将导致最多2个物品被消除）。我们负担不起2个项目，因此我们不能负担保留项目2无论其得分。消除它将解决两个决策集，并且是唯一的选择。

更一般的算法可能更复杂：在每次迭代中，您删除您负担不起的生存分数的项目，如果您没有接近这个限制，使用分数和生存分数的组合来决定哪一个必须去。