如何快速判斷此組的任何子集是否滿足此條件？

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