Major optimization - pairing widgets and rotors
I don't know much about optimization issues, 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 overall value when each widget and rotor can only be used once?
+2
a source to share
2 answers
What you have is a bidirectional max weight matching problem: on the left, you have widgets on the right, rotors, and the join weights are the point values. This Wikipedia article talks about how to solve it.
+4
a source to share
How far will you get the greedy algorithm? You can sort all pairs of the rotor widget by count and just go through the list, skipping everything that contains the 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
...
0
a source to share