如何快速判断此组的任何子集是否满足此条件？

Question

我知道这是一个NP难题，但我们很多用户一直在请求这个功能（基本上，您当前订单中的任何一组项目是否符合我们正在运行的某项交易？或者是否有任何设置的项目加上另一个项目的资格？）

由于提供的功能更多的是关于用户的便利比找到正确的答案我一直在考虑快捷方式做到这一点，而不需要花太长时间，如没有运行算法如果有超过X个项目，其中X是引起显着滞后的数量，或者只运行通过算法最近添加的X个项目。

有没有人在处理类似问题之前可以提供建议？

Answer 1

想想pidgeonhole。这种方法在所有情况下都是O（m + n）复杂度。

将每个“交易”合并为一组规则，然后遍历项目，将它们添加到每个满足其规则的pidgeonhole。

然后循环处理，从物品中拉出物品（如果物品在物品中）。

例子：

"blue car", "red car", "yellow expensive car", "red expensive car", "cheap car" 

的交易：

buy a red car, get a blue car for free 
buy an expensive car, get a cheap car for free 

的 “规则”，我们可以推断出：

is_red, is_expensive, is_blue, is_cheap 

因此，我们有2个孔，is_red和is_expensive。通过项目环，把它们添加到其规则，他们满足所有的孔，导致这些漏洞：

is_red ("red car", "red expensive car") 
is_expensive ("red expensive car", yellow expensive car") 
is_blue ("blue car") 
is_cheap ("cheap car") 

然后通过交易循环：

buy a red car, get a blue car for free 
is_red contains "red car", is_blue contains "blue car", so: 
    pop them from the holes and make them a deal 

下一笔交易：

buy an expensive car, get a cheap car for free 
is_expensive doesn't contain any cars