sql-server - 算法找到满足给定要求的最少项目

Question

我想为以下问题实现一个算法。稍后需要在以下位置实施T-SQL：

• 我有一组供应商——比如说商店。每个商店都有它提供的一组商品。有些商品在商店之间重叠，有些商品只出现在一个商店中。
• 我有一个项目列表 - 让我们说shopping一个包含一组我想要的项目的列表。

我现在必须找到提供ALL商品同时需要最少数量的商店的商店组合。

我很确定这个问题经常得到解决，并且该算法有自己的名称，但我无法通过搜索找到它。

Answer 1

对不起，我想我第一次误解了这个问题。您的问题本质上是一个NP 完全的集合覆盖问题。有启发式方法，但没有最佳解决方案。

（这与您的问题相似但不完全是您的问题，但值得一看）背包问题

Answer 2

不确定任何特定的算法。但鉴于您的要求，我会：

• 开始寻找列表中匹配商品数量最多的商店。
• 迭代直到你填满你的列表。

如果你想真正优化这个，你可以寻找任何多余的商店。冗余商店将拥有由您列表中的一个或多个其他商店提供的物品。

再想一想，这可以使用二进制线性规划来解决。每个商店都是可变的，并且约束条件是每个商品必须由至少一个商店提供服务。然后，您尝试尽量减少商店的数量。不确定如何在 T-SQL 中解决这个问题。