我正在寻找一种算法。假设我们有一个包含顶点 {A， B， C， D， E... } 的图，并且每个顶点可能有多个加权边到集合中的其他顶点(我将组成一个邻接列表作为示例(：
A: (B, 34), (C, 32), (E, 20)
B: (A, 30)
C: (C, 32), (D, 41)
D: (B, 34), (A, 30), (E, 20)
E: (D, 41)
指向同一节点的边始终具有相同的值。
我想找到边缘权重总和最大的子集(具有一定的固定长度(，其中节点的边缘只计算一次。换句话说，在此示例中，长度为 2 的最大子集是 {C， D}，值为 30 + 34 + 32 + 41 + 20 = 157(它命中所有值(。尽管具有最大的单个值，但 A 不包括在此总和中，并且将其与任何其他节点相加不会达到所有值。
为清楚起见，{C， E} 的子集为 32 + 41 = 73(D 的边不计算两次(。
通过蛮力执行此操作类似于 O(V！*lg(V((，因为最后可以找到组合和排序。有什么方法可以更有效地计算吗？
我想我会说明到目前为止我所发现的。我还没有想出任何更好的最坏情况保证，但我想出了一个修剪启发式方法，保证找到最佳解决方案。假设有名为 x 和 y 的集合，每个集合的大小为 n(x 也可以小于 y(。如果 y 是 x 的子集，则可以保证任何用 y 替换 x 的集合至少与使用 y 的集合一样好。检查任何集合是否是超集需要最坏情况的二次时间，但如果顶点预期相似(或在联合后相似(，则可能导致计算时间减少。