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

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 完全的。 set cover problem 有一个微不足道的减少通过仅将所有权重设置为 1 来解决此问题。您不会编写快速、精确的解决方案。您可以尝试近似算法、回溯搜索或现有的优化问题求解器。在 Google 上快速搜索 set cover solver 结果是 Microsoft Solver Foundation ，这可能对您有用。

如果您想自己做，并且想要一个精确的解决方案，backtracking会做的。您一次建立一个元组列表。对于每个元组，您决定是否包含它；您可以任意选择，但最好的性能来自于明智的决定。当你确定你所做的决定不能产生最佳解决方案时——也许是因为你已经超过了你之前找到的更好解决方案的重量——你回溯到你所做的最后一个决定并选择一个不同的选项。如果您选择的元组包含您想要的所有项目，您也可以回溯。如果你已经为一个决定尝试了所有的可能性，你会回到你没有尝试过所有可能性的最后一个决定。当您完全无法尝试时，您在整个过程中找到的最佳解决方案就是可能的最佳解决方案。