大家好，我是哪吒。
做技术，我是认真的，立志于打造最权威的华为OD机试真题专栏，帮助那些与我有同样需求的人（考华为OD机试，升职加薪），每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。
一、题目描述
MELON有一堆精美的雨花石(数量为n，重量各异)，准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。
二、输入描述
第1行输入为雨花石个数: n，0<n<31。
第2行输入为空格分割的各雨化石重量: m[0] m[1] … m[n- 1]， 0< m[k] < 1001
不需要考虑异常输入的情况。
三、输出描述
如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等;如果不能均分，则输出-1。
四、动态规划
看到题目，我的第一反应是采用动态规划求解，目标值是雨花石重量总和的一半，从当前雨花石中最少拿出几块，满足两人的雨花石均分。
先区分一下动态规划与分治方法，都是将原问题拆分成若干个子问题，分别求解，再组合子问题的结果选出最优解。
分治方法将问题划分为互不相交的子问题，递归的求解子问题，再将它们的解组合起来，求出原问题的解。
动态规划应用与子问题重叠的情况，即不同的子问题具有公共的子子问题（子问题的求解是递归进行的，将其划分为更小的子子问题），在这种情况下，分治方法会做许多不必要的工作，他会反复求解那些公共子子问题。
而动态规划对于每一个子子问题只求解一次，将其解保存在一个表格里面，从而无需每次求解一个子子问题时都重新计算，避免了不必要的计算工作。
五、解题思路
- 输入有几块雨花石；
- 输入每块雨花石的重量；
- 通过Java8新特性 Stream表达式获取每块雨花石的重量；
- 获取雨花石的总重量；
- 因为要两个人平分，不能平分的话，直接返回-1；
- 计算雨花石的一半重量，也就是两个人得到的重量，计算动态规划目标值；
- 定义二维数组dp，采用动态规划算法，求出最优解；
六、Java算法源码
package com.guor.od;
import java.util.Scanner;
import java.util.*;
public class OdTest {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入有几块雨花石
int n = Integer.parseInt(sc.nextLine());
// 输入每块雨花石的重量
int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 获取雨花石的总重量
int sum = Arrays.stream(nums).sum();
// 因为要两个人平分，不能平分的话，直接返回-1
if (sum % 2 != 0) {
System.out.println(-1);
return;
}
// 雨花石的一半重量，也就是两个人得到的重量，计算目标
int avg = sum / 2;
// 采用动态规划算法
int[][] dp = new int[n + 1][avg + 1];
for (int i = 0; i <= avg; i++) {
dp[0][i] = n;
}
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 1; j <= avg; j++) {
if (j < num) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - num] + 1);
}
}
}
if (dp[n][avg] == n) {
System.out.println(-1);
} else {
// 输出最优解
System.out.println(dp[n][avg]);
}
}
}
七、效果展示
1、输入
4
1 2 3 4
2、输出
2
3、说明
🏆下一篇：华为OD机试真题 Java 实现【跳房子II】【2023 B卷 100分】，附详细解题思路
🏆本文收录于，华为OD机试（JAVA）（2022&2023）
刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，订阅后，专栏内的文章都可看，可加入华为OD刷题群（私信即可），发现新题目，随时更新，全天CSDN在线答疑。