1

我知道这是一个 NP 难题，但我们的很多用户一直在请求此功能（基本上，您当前订单中的任何一组商品是否符合我们正在运行的交易之一？或者任何一组您当前订单中的商品加上其他商品是否符合条件？）

由于提供功能更多的是为了用户方便而不是找到正确的答案，我一直在考虑使用快捷方式来做到这一点而不会花费太长时间，例如如果有超过 X 个项目，则不运行算法，其中 X 是导致明显的数字滞后，或仅通过算法运行最近添加的 X 项。

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

4

1 回答 1

2

想想鱼塘。这种方法在所有情况下都是 O(m+n) 复杂度。

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

然后循环处理这些交易，如果它们在其中，则将它们从 pidgeonholes 中拉出。

例子：

"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
于 2012-03-12T05:03:09.837 回答