将n名招募人员均分为两队以最大化总效率的算法求解

嗨，我来帮你搞定这个分组问题，让总效率最大化～

我们有n名招募人员（n是偶数），每人有两个属性：

• ability_power：加入巫师队时，为团队贡献的效率值
• strength：加入战士队时，为团队贡献的效率值

需要把所有人平分成两组（各n/2人），目标是让总效率 = 战士队strength总和 + 巫师队ability_power总和最大化。

你提到的按单个属性（比如max(ability_power, strength)）排序后逐个分配的思路，在很多场景下能得到不错的结果，但并不能保证总是最优。比如遇到某些“属性互补”的人员时，只看单个最大属性分配会错过整体最优的组合。

举个典型反例：
假设有4名人员：

• 甲：ability=6，strength=1
• 乙：ability=1，strength=6
• 丙：ability=5，strength=5
• 丁：ability=5，strength=5

如果按单个属性最大值排序，顺序是乙（strength6）、甲（ability6）、丙、丁。分配后战士队是乙+丙（6+5=11），巫师队是甲+丁（6+5=11），总效率22。但如果我们换个思路，选甲和丙当巫师（差值6-1=5，5-5=0，总和5），乙和丁当战士（差值6-1=5，5-5=0，总和5），总效率其实一样。但如果遇到更极端的差值情况：

• A：ability=10，strength=1
• B：ability=9，strength=10
• C：ability=1，strength=10
• D：ability=10，strength=9

按单个属性排序的话，B(str10)、C(str10)、A(ab10)、D(ab10)，分配后战士队是B+C（10+10=20），巫师队是A+D（10+9=19），总效率39。但如果按差值排序，A的差值是9，D的差值是1，B的差值是-1，C的差值是-9，选前2个差值最大的A和D当巫师，总效率是(10+10)+(10+9)=39，结果一样。但如果有人员差值大但单个属性不突出的情况，单个属性排序就会出错。

其实我们可以把总效率的公式做个变形，找到更清晰的优化方向：

总效率 = 战士队strength总和 + 巫师队ability_power总和

我们可以把战士队的strength总和转化为所有人员的strength总和 - 巫师队的strength总和，代入公式：

总效率 = (所有strength总和 - 巫师队strength总和) + 巫师队ability_power总和
= 所有strength总和 + (巫师队ability_power总和 - 巫师队strength总和)
= 所有strength总和 + Σ(ability_power_i - strength_i) （仅针对巫师队成员）

因为所有strength总和是固定值，所以最大化总效率等价于：选出n/2名人员作为巫师队，使得他们的(ability_power - strength)差值总和最大。

反过来，如果你想从战士队的角度出发，也可以推导：

总效率 = 战士队strength总和 + (所有ability_power总和 - 战士队ability_power总和)
= 所有ability_power总和 + Σ(strength_i - ability_power_i) （仅针对战士队成员）

也就是选出n/2名人员作为战士队，使得他们的(strength - ability_power)差值总和最大。

具体步骤 #

1. 给每个人员计算差值：diff = ability_power - strength（用于选巫师队），或者diff = strength - ability_power（用于选战士队）
2. 按差值从大到小排序所有人员
3. 取前n/2个差值最大的人员作为巫师队（对应第一种推导），剩下的作为战士队；或者取前n/2个作为战士队（对应第二种推导）
4. 计算总效率即可

代码示例（Python） #

class Recruit:
    def __init__(self, ability_power, strength):
        self.ability_power = ability_power
        self.strength = strength

def max_total_efficiency(recruits):
    n = len(recruits)
    assert n % 2 == 0, "n必须是偶数"
    
    # 按(ability_power - strength)降序排序，选前n/2个当巫师
    sorted_recruits = sorted(recruits, key=lambda x: (x.ability_power - x.strength), reverse=True)
    
    wizard_team = sorted_recruits[:n//2]
    warrior_team = sorted_recruits[n//2:]
    
    total_efficiency = sum(r.strength for r in warrior_team) + sum(r.ability_power for r in wizard_team)
    return total_efficiency

# 测试用例
recruits = [
    Recruit(10, 1),
    Recruit(9, 10),
    Recruit(10, 9),
    Recruit(1, 10)
]
print(max_total_efficiency(recruits))  # 输出39，为最优结果

这个方法的时间复杂度主要由排序决定，是O(n log n)，对于大多数场景来说效率足够。

内容的提问来源于stack exchange，提问作者bordus