将 "people" 分成两个人数相等的团队以达到最大总效率

Question

我正在尝试解决这个任务：

The kingdome recruited n people. Recruit has two characteristics: ability 
power and strength. Recruits must be devided into two equal-size squads: 
warriors and wisards. Found separation with max efficiency level.  Efficiency 
of wizard is determined by ability-power, of warrior - by strength.

我的第一个想法是按最大参数（或使用 max_heap）对新兵进行排序，然后：

for recruit in sorted_recruits:
     if wisards_counter!=n/2 or warriors_counter!=n/2:
            if recruit.strength>recruit.ap:
                summ+=recruit.strength
                warriors_counter+=1
            elif recruit.strength<recruit.ap:
                summ+=recruit.ap
                wisards_counter+=1

但后来我明白这是错误的做法。也许有人可以建议一个好的数据结构和启发式来解决这个任务？

顺便说一句，任务的第二部分意味着可以更改（增加）新兵的参数，我们应该重新改造团队以再次获得最大值。但首先要至少先解决。将不胜感激！

Answer 1

这个问题可以用本地优化器解决：

从将新兵随机分配到两个 equally-sized 组开始，并让他们按照效率增益进行排序。效率增益是指将新兵移至另一组时所获得的效率增益。对于法师组新兵来说，就是strength - ability；另一组则相反

然后，反复交换两名新兵（每组一名），直到无法再改进为止。找到交换候选者非常容易：只需选择效率增益最高的两个候选者即可。如果效率增益之和变为负数，则您已找到最佳分配。

将 "people" 分成两个人数相等的团队以达到最大总效率

Divide "people" into two equal-size teams to reach max total efficiency

algorithm

heap

data-structures

segment-tree