青岛公司网站建设价格,迅捷在线图片编辑,云服务器有哪些,wordpress主题 已存在题目 MELON有一堆精美的雨花石(数量为n#xff0c;重量各异)#xff0c;准备送给S和W。MELON希望送给俩人的雨花石重星一致#xff0c;请你设计一个程序帮MELON确认是否能将雨花石平均分配。 输入描述 第1行输入为雨花石个数:n#xff0c;0n 31. 第2行输入为空格分…题目 MELON有一堆精美的雨花石(数量为n重量各异)准备送给S和W。MELON希望送给俩人的雨花石重星一致请你设计一个程序帮MELON确认是否能将雨花石平均分配。 输入描述 第1行输入为雨花石个数:n0n 31. 第2行输入为空格分割的各雨花石重量: m[0] m[1 ]… m[n - 1], 0m[k]1001不需要考虑异常输入的情况。 输出描述 如果可以均分从当前雨花石中最少拿出几块可以使两堆的重量相等: 如果不能均分则输出-1。 示例1: 输入 4 1 1 2 2 输出 2 说明 输入第一行代表共4颗雨花石第二行代表4颗雨花石重量分别为1、1、2、2。均分时只能分别为1,2需要拿出重星为1和2的两块雨花石所以输出2。 示例2: 输入 10 1 1 1 1 1 9 8 3 7 10 输出 3 说明 输入第一行代表共10颗雨花石第二行代表4颗雨花石重量分别为1、1、1、1、1、9、8、3、7、10。均分时可以1,1,1,1,1,9,7和10,8,3也可以1,1,1,1,9.8和10,7,3,1或者其他均分方式但第一种只需要拿出重量为10.8,3的3块雨花石第二种需要拿出4块,所以输出3(块数最少)。 思路
两个方案
排列组合
排列组合思路参照模板【JAVA-排列组合】一个套路速解排列组合题 针对本题而言简要分析如下 首先计算雨花石的重量总和sumsum不能被2整除直接返回-1。能被2整除那么我们至少需要拿出多少块雨花石使其重量和targetsum/2。 要求最少数量先拿重量较大的雨花石所以可以将输入nums降序排列剪枝分析如下 雨花石重量可能存在重复注意同层相同剪枝如果某个组合的雨花石重量在加入下一个雨花石之前已经不小于target或者组合个数已经不小于之前解的个数直接剪枝 最后注意因为要求的res为最小值初始值设置的Integer.MAX_VALUE 如果没有找到合适的组合res还是等于Integer.MAX_VALUE那么最后需要返回-1. 动态规划 定义 dp[i][j]的含义为在前i个雨花石选择使其重量和等于j需要的最少雨花石个数。 初始化 dp[i][0]要使目标和等于0那么选0个即可所以dp[i][0]0其中i的范围为0~nums.length-1 dp[0][j]从前0个元素选即只有nums[0]可选目标和就是nums[0],使其累加和为jj的范围为0~target如果jnums[0]那么dp[0][j]1否则给其一个初始值。具体初始值给多少? 比如nums为2 3 4 5dp[0][2]1。dp[0][3]不可能满足只选2不可能使其和等于3可以将其结果设置为一个比较大的值因为最后取的最小值如果存在一个满足条件的值两相比较就能得到最小结果。这里我设置为nums.length。 递推关系 对于dp[i][j]i0,j0,只有两种情况当前值选和当前值不选 当前值选dp[i][j]dp[i-1][j-nums[i]]1 当前值不选: dp[i][j]dp[i-1][j] 结果中两者取其小即可。同时需要注意如果当前值比目标j还大那肯定走不选的分支 根据初始化和递推关系最后求得dp[nums.length-1][target]如果其值等于nums.length即初始化的值说明不存在这样的组合直接返回-1。 题解
排列组合
package hwod;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class YuhuaStone {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n Integer.parseInt(sc.nextLine());int[] nums new int[n];for (int i 0; i n; i) {nums[i] sc.nextInt();}System.out.println(yuHuaStone(nums));}private static int res Integer.MAX_VALUE;private static int yuHuaStone(int[] nums) {int sum Arrays.stream(nums).sum();if (sum % 2 ! 0) return -1;int target sum / 2;int[] used new int[nums.length];LinkedListInteger path new LinkedList();Arrays.sort(nums);dfs(nums, nums.length - 1, path, used, target);return res Integer.MAX_VALUE ? -1 : res;}private static void dfs(int[] nums, int start, LinkedListInteger path, int[] used, int target) {if (target 0) {res Math.min(res, path.size());return;}for (int i start; i 0; i--) {if (target 0 || path.size() res) break;if (i nums.length - 1 nums[i 1] nums[i] used[i 1] 0) continue;path.addLast(nums[i]);used[i] 1;dfs(nums, i - 1, path, used, target - nums[i]);path.removeLast();used[i] 0;}}
}
动态规划
package hwod;import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;public class YuhuaStone {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n Integer.parseInt(sc.nextLine());int[] nums new int[n];for (int i 0; i n; i) {nums[i] sc.nextInt();}System.out.println(yuHuaStone(nums));}private static int yuHuaStone(int[] nums) {int sum Arrays.stream(nums).sum();if (sum % 2 ! 0) return -1;int target sum / 2;int size nums.length;int[][] dp new int[size][target 1];for (int j 0; j target 1; j) {if (j nums[0]) dp[0][j] 1;else dp[0][j] size;}for (int i 1; i size; i) {for (int j 1; j target; j) {if (nums[i] j) dp[i][j] dp[i - 1][j];else dp[i][j] Math.min(dp[i - 1][j], 1 dp[i - 1][j - nums[i]]);}}int res dp[size - 1][target];return res size ? -1 : res;}
}
用例
补充输出-1的用例
用例一
6 2 5 5 6 7 10
用例二
3 2 3 3
推荐
如果你对本系列的其他题目感兴趣可以参考华为OD机试真题及题解JAVA查看当前专栏更新的所有题目。
