华为OD机试 - 篮球比赛 - 递归（Java 2024 E卷 100分）

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

篮球(5V5)比赛中，每个球员拥有一个战斗力，每个队伍的所有球员战斗力之和为该队伍的总体战斗力。

现在10个球员准备分为两队进行训练赛，教练希望2个队伍的战斗力差值的绝对值尽可能的小，以达到最佳训练效果。

给出10个球员的战斗力，如果你是教练，你该如何分队，才能达到最佳训练效果？请说出该分队方案下的最小战斗力差值。

二、输入描述

10个篮球队员的战斗力(整数，范围[1,10000])，战斗力之间用空格分隔，如: 10 9 8 7 6 5 4 3 2 1
不需要考虑异常输入的场景。

三、输出描述

最小的战斗力差值，如: 1

四、测试用例

测试用例1：

1、输入

10 9 8 7 6 5 4 3 2 1

2、输出

3、说明

1 2 5 9 10分为一队，3 4 6 7 8分为一队，两队战斗力之差最小，输出差值1。备注：球员分队方案不唯一，但最小战斗力差值固定是1

测试用例2：

1、输入

1 1 1 1 1 1 1 1 1 1

2、输出

3、说明

所有球员战斗力相同，任意分队差值为0。

五、解题思路

在递归过程中选择或不选择当前球员，构建所有可能的组合。

递归回溯能够有效地遍历所有可能的组合，适用于小规模问题。

使用 Scanner 从标准输入读取10个整数，代表10个球员的战斗力，并存储在 strengths 数组中。
遍历 strengths 数组，计算所有球员的总战斗力 totalSum。
设置 minDifference 为 Integer.MAX_VALUE，用于存储最小的战斗力差值。
使用递归函数 findMinDifference 生成所有可能的5人组合。
对于每一个5人组合，计算其战斗力和 currentSum，然后计算差值 |2*currentSum - totalSum|。
更新 minDifference，保持最小的差值。
最终输出 minDifference，即最小的战斗力差值。

六、Java算法源码

public class OdTest {public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 读取10个球员的战斗力，并存储在数组中int[] strengths = new int[10];for (int i = 0; i < 10; i++) {strengths[i] = sc.nextInt();}// 计算所有球员的总战斗力int totalSum = 0;for (int strength : strengths) {totalSum += strength;}// 初始化最小差值为一个很大的数int minDifference = Integer.MAX_VALUE;// 使用递归生成所有5人组合，并计算最小差值minDifference = findMinDifference(strengths, 0, 0, 0, 5, totalSum, minDifference);// 输出最小战斗力差值System.out.println(minDifference);sc.close();}/*** 递归函数，生成所有5人组合，并计算最小差值* @param strengths 球员战斗力数组* @param index 当前考虑的球员索引* @param currentSum 当前组合的战斗力和* @param count 当前组合中的球员数量* @param target 目标球员数量（5人）* @param totalSum 所有球员的总战斗力* @param minDifference 当前最小差值* @return 更新后的最小差值*/private static int findMinDifference(int[] strengths, int index, int currentSum, int count, int target, int totalSum, int minDifference) {// 当组合达到目标人数时，计算差值if (count == target) {int difference = Math.abs((2 * currentSum) - totalSum);return Math.min(minDifference, difference);}// 如果剩余球员不足以完成目标组合，返回当前最小差值if (index >= strengths.length) {return minDifference;}// 选择当前球员加入组合minDifference = findMinDifference(strengths, index + 1, currentSum + strengths[index], count + 1, target, totalSum, minDifference);// 不选择当前球员，继续递归minDifference = findMinDifference(strengths, index + 1, currentSum, count, target, totalSum, minDifference);return minDifference;}
}

七、效果展示

1、输入

1 5 7 1 9 33 20 11 55 100

2、输出

3、说明

计算所有球员的总战斗力：1 + 5 + 7 + 1 + 9 + 33 + 20 + 11 + 55 + 100 = 242
理想情况下，我们希望将总战斗力尽量平均分配到两个队伍中，即每个队伍的战斗力接近：242 / 2 = 121
因此，我们的目标是找到一个5人组合，使其战斗力和尽可能接近121，从而使得另一个队伍的战斗力和也接近121，最终实现最小的差值。
为了达到最小差值，我们需要找到一个5人组合，其战斗力和为120或122
经过仔细组合和计算，我们发现以下分组方案能够达到最小差值2：
- 100, 1, 1, 7, 11 = 120
- 5, 9, 20, 33, 55 = 122

通过上述分组，我们达到了两个队伍的战斗力和分别为120和122，差值为2。

在这里插入图片描述