【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号位。这样评分就是95而最高显然是78。贪心的本质是局部最优推算到全局最优但对于这种指派问题难以由局部推向全局最优。且要考虑的条件较多情况复杂。故在此我们暂时舍弃贪心算法。三 DFS思路若利用深度搜索思路就比较清晰了我们穷尽所有情况如果选中了5个球员直接返回并且更新最大的评分。其中我们需要建立一个访问数组vist来保证不会出现重复选择的情况。四 DFS代码复现以上就是我的思路以及代码代码中穿插了所需要注意的细节。欢迎各位讨论