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

ウィジェットの数とローターの数が固定されている場合、各ウィジェットとローターを1回しか使用できない合計値を最大化する、一連のウィジェットとローターのペアを取得するにはどうすればよいでしょうか。

Answer 1

持っているのは、最大加重2部マッチングの問題です。左側にはウィジェットがあり、右側にはローターがあり、接続の重みはポイント値です。このウィキペディアの記事では、それを解決する方法について説明します。

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