題目

MELON有一堆精美的雨花石(數(shù)量為n，重量各異)，準(zhǔn)備送給S和W。MELON希望送給倆人的雨花石重星一致，請你設(shè)計一個程序幫MELON確認(rèn)是否能將雨花石平均分配。
輸入描述
第1行輸入為雨花石個數(shù):n，0<n <31.
第2行輸入為空格分割的各雨花石重量: m[0] m[1 ]… m[n - 1], 0<m[k]<1001不需要考慮異常輸入的情況。
輸出描述
如果可以均分，從當(dāng)前雨花石中最少拿出幾塊，可以使兩堆的重量相等:
如果不能均分，則輸出-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(塊數(shù)最少)。

思路

兩個方案：

排列組合

排列組合思路參照模板：【JAVA-排列組合】一個套路速解排列組合題

針對本題而言，簡要分析如下：
首先計算雨花石的重量總和sum，sum不能被2整除，直接返回-1。能被2整除，那么我們至少需要拿出多少塊雨花石，使其重量和target=sum/2。
要求最少數(shù)量，先拿重量較大的雨花石，所以可以將輸入nums降序排列，剪枝分析如下：

1. 雨花石重量可能存在重復(fù)，注意同層相同剪枝
2. 如果某個組合的雨花石重量在加入下一個雨花石之前，已經(jīng)不小于target或者組合個數(shù)已經(jīng)不小于之前解的個數(shù)，直接剪枝

最后注意，因為要求的res為最小值，初始值設(shè)置的Integer.MAX_VALUE ，如果沒有找到合適的組合，res還是等于Integer.MAX_VALUE，那么最后需要返回-1.

動態(tài)規(guī)劃

定義：

dp[i][j]的含義為：在前i個雨花石選擇，使其重量和等于j，需要的最少雨花石個數(shù)。

初始化：

dp[i][0]，要使目標(biāo)和等于0，那么選0個即可，所以dp[i][0]=0，其中i的范圍為：0~nums.length-1
dp[0][j]，從前0個元素選（即只有nums[0]可選，目標(biāo)和就是nums[0]）,使其累加和為j（j的范圍為0~target），如果j=nums[0]，那么dp[0][j]=1，否則給其一個初始值。具體初始值給多少? 比如nums為：2 3 4 5，dp[0][2]=1。dp[0][3]不可能滿足（只選2，不可能使其和等于3），可以將其結(jié)果設(shè)置為一個比較大的值（因為最后取的最小值，如果存在一個滿足條件的值，兩相比較就能得到最小結(jié)果）。這里我設(shè)置為nums.length。

遞推關(guān)系：
對于dp[i][j]（i>0,j>0）,只有兩種情況，當(dāng)前值選和當(dāng)前值不選

當(dāng)前值選：dp[i][j]=dp[i-1][j-nums[i]]+1
當(dāng)前值不選: dp[i][j]=dp[i-1][j]
結(jié)果中兩者取其小即可。同時需要注意，如果當(dāng)前值比目標(biāo)j還大，那肯定走不選的分支
根據(jù)初始化和遞推關(guān)系，最后求得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];LinkedList<Integer> 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, LinkedList<Integer> 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;}}
}

動態(tài)規(guī)劃

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），查看當(dāng)前專欄更新的所有題目。