algorithm - 基本优化——配对小部件和转子

Question

我对优化问题知之甚少，所以希望这对我有指导意义：

rotors = [1, 2, 3, 4...]
widgets = ['a', 'b', 'c', 'd' ...]

assert len(rotors) == len(widgets)

part_values = [
(1, 'a', 34),
(1, 'b', 26),
(1, 'c', 11),
(1, 'd', 8),
(2, 'a', 5),
(2, 'b', 17),
....
]

给定固定数量的小部件和固定数量的转子，如何获得一系列小部件-转子对，使每个小部件和转子只能使用一次的总价值最大化？

Answer 1

您所拥有的是最大加权二分匹配问题：在左侧，您有小部件，在右侧，转子，连接的权重是点值。这篇维基百科文章介绍了如何解决它。

Answer 2

贪心算法能让你走多远？您可以按分数对所有小部件-转子对进行排序，然后简单地沿着列表向下走，跳过任何包含已使用的小部件或转子的内容。例子：

2-b = 40  # yes
2-c = 30  # no, already used rotor 2
1-a = 20  # yes
4-a = 10  # no, already used widget a
3-c = 5   # yes
...