找到具有最低分数的所需项目的集合

Question

我正在解决一个问题,而且我在某个方面遇到了我的数据结构.这是问题所在:

我有一个n 元组列表(每个元组包含一组项目和与该组相关的权重).元组内的集合可以包含任意数量的项目(或根本没有项目).另外,我有一套包含所有需要的项目.让我举一个数据样本,以进一步澄清:

desired_set = set(['item1', 'item2', 'item3'])

list_of_tuples = [
                  (12.0, set(['item1', 'item3'])),
                  (3.5, set(['item3'])),
                  (5.0, set(['item2'])),
                  (7.2, set(['item1'])),
                  (10.0, set(['item2', 'item3']))
                 ]

现在,我需要组合这些集合以获得所有可能的所需集合.当这些组合在一起时,它们的重量将会增加.例如,对于以上数据:

(12.0, set(['item1', 'item3']))并(5.0, set(['item2']))会给(17.0, set(['item1', 'item2', 'item3']))

(5.0, set(['item1'])),(7.2, set(['item2']))并(3.5, set(['item3']))会给(15.7, set(['item1', 'item2', 'item3']))

(7.2, set(['item1']))并(10.0, set(['item2', 'item3']))会给(17.2, set(['item1', 'item2', 'item3']))

我需要在新列表中获取所有这些可能的元组(其中set与desired_set相同),以便我可以找到具有最小分数的元组.非常感谢任何帮助(代码,算法,建议,指导).

Answer 1

这是NP完全的.只需将所有权重设置为1,就可以将集合覆盖问题轻微减少到这个问题.您不会编写快速,准确的解决方案.您可以尝试近似算法,回溯搜索或现有优化问题求解器.快速谷歌搜索set cover solver变成了微软求解基金会,这可能会为你工作.

如果你想自己做这件事,并且你想要一个精确的解决方案,那么回溯会做到这一点.您可以一次构建一个元组列表.对于每个元组,您决定是否包含它; 你可以任意选择,虽然最佳表现会来自智能决策.当您确定您所做出的决策无法产生最佳解决方案时 - 可能是因为您已经超出了之前找到的更好解决方案的权重 - 您回溯到最后做出的决定并选择其他选项.如果您选择的元组包含您想要的所有项目,您也会回溯.如果您已经尝试了所有可能的决策,那么您将回到最后一个未尝试过所有可能性的决定.如果您完全没有尝试,那么您在整个过程中找到的最佳解决方案是最佳解决方案.