代码之家  ›  专栏  ›  技术社区  ›  ʞɔıu

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

  •  2
  • ʞɔıu  · 技术社区  · 14 年前

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

    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 回复  |  直到 10 年前
        1
  •  4
  •   interjay    14 年前

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

        2
  •  0
  •   Michael Kristofik    14 年前

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

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