Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
我有一组值,每个值都有一个可能的组。该值可以重复但在不同的组中。
什么是获得最少组数的最佳算法
一个样本集:(12,b组)(38,a组)(12,a组)
预期结果:(38,a 组)(12,a 组)
(仅使用一组)
-- 编辑:我需要一个算法来从上面的示例中找到最小数量的组。如果我的算法不好,它将选择(12,b组)(38,a组)这是相同值的2组,而不是使用一个,不是我想要的
如果我正确理解了这个问题,这就是Set cover 问题
链接中描述的贪心算法从组 a 开始,然后终止,因为这已经涵盖了所有内容。
请注意,通常它只产生最佳解决方案的近似值。