javascript - 如何在给定一些规则的情况下最大化对象组合的值(value)

Question

我有一个包含 Angular 色列表的模块对象。这些 Angular 色可以代表一个或多个 Angular 色(Es: "RoleA", or maybe "RoleA;RoleB")

// Example

var roles = [      
    'Por',
    'Ds',
    'Dc',
    'Dc',
    'Dd',
    'M',
    'M;C',
    'T',
    'W',
    'W;A',
    'A;Pc'
]

我有另一个数组。这是玩家对象的列表。每个玩家都有一个“Angular 色”和一个“值(value)”。 Angular 色也可以是单个或多个。

// Example

var players = [  
{    
    name: 'NameA',
    role : 'A',
    value: 15
},
{    
    name: 'NameB',
    role : 'A;W',
    value: 15
},
{    
    name: 'NameC',
    role : 'Dd;Dc',
    value: 15
},
...
]

我的目标是为“Angular 色”数组的每个 Angular 色分配一名球员，使球队的总值(value)最大化(通过将单个球员的值(value)相加计算得出)

我已经完成了对 Angular 色数组的迭代，试图每次都找到最佳选择。我通过添加一些简单的机制解决了一些问题，但在某些情况下，我仍然遇到一些问题。

任何了解算法的人都可以解释一下面对这类问题的最佳方法是什么吗？

    // Example

    var roles = [      
    ['Por', playerA],
    ['Ds', playerB],
    ['Dc', playerC],
    ['Dc', playerD],
    ['Dd', playerE],
    ['M', playerF],
    ['M;C', playerG],
    ['T', playerH],
    ['W', playerI],
    ['W;A', playerL],
    ['A;Pc, playerM]
    ]

Answer 1

这个问题被称为:最大二部加权匹配。你可以解决它减少到最大流量问题。

想法是创建这样一个图:

• 顶点:玩家和 Angular 色
• 边:将玩家与 Angular 色数组中的可能 Angular 色联系起来(从 Angular 色到玩家的方向)

接下来要做什么在 this 的公认答案中有很好的描述问题。

其他资源

最大流量问题:link