代码之家 › 专栏 › 技术社区 › ÊÉÄ±u

基本优化-配对部件和转子

mathematical-optimization algorithm

ÊÉÄ±u · 技术社区 · 15 年前

我对优化问题知之甚少,所以希望这对我来说是一种教诲:

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

给定一个固定数量的小部件和一个固定数量的转子,如何获得一系列的小部件转子对,使每个小部件和转子只能使用一次的总值最大化?

2 回复 | 直到 11 年前

interjay 15 年前

您所拥有的是一个最大加权的二部分匹配问题:在左侧,您有小部件,在右侧,转子,连接的权重是点值。这个 Wikipedia article 研究如何解决它。

Michael Kristofik 15 年前

贪婪的算法能让你走多远?您可以按分数对所有的小部件转子对进行排序,然后简单地沿着列表走下去,跳过任何包含已经使用的小部件或转子的小部件。例子:

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

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

4 月前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

5 月前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

5 月前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

5 月前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

6 月前

b39b332d · 使用C++标准库实现高效间隔存储

9 月前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

9 月前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

9 月前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

9 月前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

10 月前