筛选列表受限制

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项(第一类，作者11)

然后我的解决方案将是

• Item3已丢弃，因为它具有与Item1和Item2相同的category
• Item4被丢弃，因为它具有与Item2相同的author
• 剩下9个其它元件

并且这不满足CCD_ 23。正确的解决方案是丢弃Item2，并且只应保留10个元素。

问题

我认为我的解决方案只是朝着错误的方向发展。因此，我正在寻找其他解决方案来解决这个问题。任何产生所需输出的解决方案都值得赞赏。

Answer 1

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

为了支持从最初的项目长度Y(在您的示例中为11)中选择一组大小至少为X(在本例中为10)的项目，您需要收集一个决策集列表，而不是仅通过分数来消除项目。决策集(m，n)是一组由m个项目组成的集合，您必须从中选择保留n个项目并消除其余项目。由于您系统中的大多数规则都是属性x的单个项目，因此您列表中的大多数决策集都将被设置(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项(第一类，作者11)

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

• 作者决策集(2,1)=｛项目2(2)，项目4(1)｝
• 类别决策集(3,2)=｛项目1(1)、项目2(2)、项目3(1)｝

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

更通用的算法可能更复杂：在每一次迭代中，你都会消除那些生存分数你负担不起的项目，如果你没有接近这个极限，那么就使用分数和生存分数的组合来决定必须选择哪一个。

Answer 2

您有一个项目列表，需要删除其中一些项目才能实现目标。您需要检查删除每个候选项目是否可以为您提供更好的解决方案！试着删除每一个可以改善你的列表的项目，看看你是否达到了目标。

以下是使用递归解决问题的步骤：

1. 如果给定的列表大小小于或等于10，则返回
2. 构建要从列表中删除的候选列表(在您的示例中为项目1、项目2、项目3和项目4)如果候选列表为空，则完成
3. 逐个删除每个候选项，调用递归，然后放回删除的项
4. 如果递归返回true，则完成

这里有一些伪代码

bool recurse(list l)
if (l.size() <= 10) {
// cannot remove anything
return false
candidates = buildCandidateList(l)
if (candidates.size() == 0)
// check for top 10 items
return true
for each c in candidates {
remove c from l
if (recurse(l) == true) 
// check for top 10 items
return true
add c back into l
}
// just get first 10 items
return false

此解决方案基于递归回溯。或者，我认为也可以建立自下而上的动态编程解决方案，这将在Big-O复杂性时间方面提供更好的结果。

Answer 3

我认为您的解决方案非常好，更不用说效率了，但是，您并没有遇到选择下一个得分最高的人是最佳解决方案的情况。在这种情况下，只有当选择一个项目会导致少于10个项目的前10名列表时，才会发生这种情况。

决策集(如@Assafs所建议的)会起作用；然而，对于问题的一般情况，通用决策集算法是非常无效的。如果你必须为数百万个条目建立完整的决策集，只是为了避免没有足够的输入项的情况，这对我来说似乎有些过头了。

此外，对"前10名"结果集的描述并不能揭示在所有情况下什么是正确的结果集。例如，如果在您给出的示例中有更多的项，则没有任何内容表明删除项2是正确的方法。目前还不清楚我们应该如何衡量哪10个是"前10名"。

我建议在你的算法中添加一个部分决策过程，一方面不会影响性能，另一方面，它将提供解决短输入问题的方法。

要实现这一点，你需要保留一个从你已经选择的每个项目到它导致被取消资格的项目的映射。最重要的是，你需要保留一个从每个不合格项目到取消其资格的项目的映射。
从贪婪算法中获得结果集后，如果你的结果少于10个，你可以查看结果集，并用取消其资格项目替换取消许多项目资格的项目
您决定首先检查哪些项目的方式实际上取决于您，因为同样，没有关于如何确定"前十名"的说明。你可以先删除那些不符合1个以上其他项目的低分项目，或者寻找最不符合条件的项目，等等。
重要的是，无论你选择什么算法，你的结果集最多有10个项目，因此，即使你提出了一个超一流的O(n^3)算法，它仍然是一个恒定的1000运算算法，实际上是O(1)。在运行初始算法的过程中，构建实现这一点所需的映射也需要O(1)时间。