【C++算法】DFS深度搜索-组队问题

本题取自蓝桥杯19年省赛

一 原题复现

现有20名球员，给定他们各自在5个位置的评分。

从中选取5名球员

求评分最高的组合方式

二 贪心算法是否可行

乍一看这题，貌似可以利用贪心算法进行选择--每个位置选出评分最高的人。那么问题来了，如果一个人同时在两个位置评分都是最高的该怎么选呢？从中选出一个最高的，再在另一个位置选择第二高的？显然不行。难以保证两个位置评分之和最高。举个例子：球员a={1,2,6,7,9}，b={1,2,5,5,8}。假设球员a在4,5号位评分最高，b在4号位评分第二高。按照刚才的思路，我们应该选择a来5号位，b来4号位。这样评分就是9+5，而最高显然是7+8。贪心的本质是局部最优，推算到全局最优，但对于这种指派问题，难以由局部推向全局最优。且要考虑的条件较多情况复杂。故在此我们暂时舍弃贪心算法。

三 DFS思路

若利用深度搜索，思路就比较清晰了，我们穷尽所有情况，如果选中了5个球员直接返回，并且更新最大的评分。其中我们需要建立一个访问数组vist，来保证不会出现重复选择的情况。

四 DFS代码复现

以上就是我的思路，以及代码，代码中穿插了所需要注意的细节。欢迎各位讨论