Need help with basic optimization problem

Question

I know little of optimization problems, so hopefully this will be didactic for me:

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),
....
]

Given a fixed number of widgets and a fixed number of rotors, how can you get a series of widget-rotor pairs that maximizes the total value where each widget and rotor can only be used once?

Answer 1

What you have is a maximum weighted bipartite matching problem: on the left, you have widgets, on the right, rotors, and the weights of the connections are the point values. This Wikipedia article goes into how to solve it.

Answer 2

How far would a greedy algorithm get you? You could sort all widget-rotor pairs by score and simply walk down the list, skipping any that contained an already-used widget or rotor. Example:

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
...