Базовая оптимизация - сопряжение виджетов и роторов

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