找到满足给定需求的最少数量的项目。
找到满足给定需求的最少数量的项目。
提问于 2013-06-07 18:32:20
我想为下面的问题实现一个算法。稍后需要在T-SQL中实现
- 我有一套提供商，--比如说商店。每家商店都有一套它提供的商品。有些商品重叠在商店之间，有些只有在一个商店。
- 我有一个项目列表-让我们说一个包含一组我想要的项目的
shopping列表。
现在我必须找到商店的组合，这些商店提供ALL的商品，而所需的商店数量最少。
我确信这个问题经常得到解决，而且算法有自己的名字，但我无法通过搜索找到它。
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-06-07 18:40:48
对不起，我想我第一次误解了这个问题。你的问题本质上是一个集合覆盖问题，它是NP-完全的.有一些启发式方法，但是没有最优解。
(这类似，但不完全是您的问题，值得一看) 背包问题
Stack Overflow用户
发布于 2013-06-07 18:37:25
不确定任何特定的算法。但考虑到你的要求，我会：
- 从你的清单上开始寻找数量最多的匹配商品的商店。
- 迭代直到你填写你的列表。
如果你真的想优化这一点，你可以找任何多余的商店。多余的商店会有一个或多个在你的名单上的其他商店提供的物品。
再想一想，这个问题可以用二元线性规划来解决。其中每个商店都是可变的，并且约束条件是每个商品必须由至少一个商店提供服务。然后，尽量减少商店的数量。不确定如何在T中解决这个问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/16990725
复制相关文章
相似问题
腾讯云开发者
