佛山建设工程交易中心网站,辽阳做网站公司,发布任务注册app推广的平台,做支付网站目录 一、题目描述二、输入描述三、输出描述四、动态规划五、解题思路六、Java算法源码七、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中#xff0c;刷题点这里 一、题目描述
MELON有一堆精美的雨花石(数量为n#xff0c;重量各异)#xff0c;准备送给… 目录 一、题目描述二、输入描述三、输出描述四、动态规划五、解题思路六、Java算法源码七、效果展示1、输入2、输出3、说明 华为OD机试 2023B卷题库疯狂收录中刷题点这里 一、题目描述
MELON有一堆精美的雨花石(数量为n重量各异)准备送给S和W。MELON希望送给俩人的雨花石重量一致请你设计一个程序帮MELON确认是否能将雨花石平均分配。
二、输入描述
第1行输入为雨花石个数: n0n31。 第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();// 因为要两个人平分不能平分的话直接返回-1if (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 实现【简易内存池】【2023 B卷 200分 考生抽中题】
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
