基本优化-将小部件和转子配对 [英] Basic optimization -- pairing widgets and rotors

问题描述

我对优化问题知之甚少，因此希望这对我有帮助:

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?

推荐答案

您所面临的是最大的加权二分匹配问题:左边是小部件，右边是转子，转子和连接的权重是点值. Wikipedia文章介绍了如何解决它.

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.

这篇关于基本优化-将小部件和转子配对的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！