java - 限制条件下的过滤列表

Question

描述

输入是List<Item>按分数排序，Item看起来像:

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

现在我需要从数组中选择得分最高的 10 个元素，在这些限制下:

• 他们应该有不同的poi
• 他们应该有不同的author
• 同一个 category 最多有 3 个项目.以及来自相同 category 的任何子序列的长度不应超过 2。

如果不存在满足上述规则的子序列，则只返回前10个元素。

我尝试过的

现在，我直接遍历 List ，并使用三个 HashMap<String, Integer>存储每个 cagetory/poi/author 的外观.我用 List<Item> selected存储结果。

• 如果已经有一个选择的元素有这个poi , 则新元素将被丢弃。
• 如果已经有一个选择的元素有这个author , 则新元素将被丢弃。
• 如果已经有三个选定元素具有此 category , 则新元素将被丢弃。
• 如果selected的尾部已经有两个元素了有这个 category , 则新元素将被丢弃。

问题

输入大的时候可以，输入比较小的时候就不行了。例如，当输入是

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(类别 I，作者 11)

那么我的解决办法就是

• Item3丢弃，因为它有相同的category作为Item1和 Item2
• Item4丢弃，因为它有相同的author作为Item2
• 其他 9 个元素保留。

这不满足 select top 10 elements .正确的解决方案是丢弃 Item2并且应该只保留 10 个元素。

问题

我认为我的解决方案方向错误。所以我正在寻找其他解决方案来处理这个问题。任何产生所需输出的解决方案都值得赞赏。

Answer 1

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

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

完整项目集的第一次传递将填充决策集列表，第二次传递将遍历该列表并从每个决策集中选择要从原始集中消除的项目。一旦做出决定并从原始集中删除项目，决策集就会从列表中删除(已解决)。清除决策集列表后，您的原始集就是合法的。

目标是在最多 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(类别 I，作者 11)

我们编译的决策集是(注意括号中的生存分数):

• 作者决策集 (2,1) = {item 2 (2), item 4 (1)}
• 类别决策集(3,2) = {item 1(1), item 2(2), item 3(1)}

我们的目标是在最多 1 次淘汰中解决决策集列表。您可以看到所有项目的生存分数都是 1(这意味着保留它们将导致最多 1 个其他项目被淘汰)除了生存分数为 2 的项目 2 >(保留它最多会消除 2 个项目)。我们负担不起 2 个项目，因此无论其得分如何，我们都不能保留项目 2。消除它会解决两个决策集，并且是唯一的选择。

更通用的算法可能更复杂:在每次迭代中，您都会消除生存分数无法承受的项目，如果您不接近该限制，请结合使用 score 和 survival-score 来决定必须去哪一个.