MELON的难题
题目描述
MELON 有一堆精美的雨花石(数量为n，重量各异)，准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。
输入描述
第1行输入为雨花石个数:n，0<n<31。
第2行输入为空格分割的各雨花石重量:m[0]m[1]… m[n -1]，0<m[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(块数最少)。
题解
这里要求是平分，所以重量必须是偶数
使用动态规划求解
初始化动态数组 dp[n][sum / 2] 初始值 Integer.MAX_VALUE / 2
if (j == weights[i]) {dp[i][j] = 1; // 恰好该重量合适
} else if (j > weights[i]) {// 重量不足，但是加上另一块石头组合后满足dp[i][j] = Math.min(dp[i][j], dp[i-1][j-weights[i]]+1);
}
源码 Java
public class YuhuaStone {static Input input;static {input = new Input("10\n" +"1 1 1 1 1 9 8 3 7 10");input = new Input("4\n" +"1 1 2 2");}public static void main(String[] args) {int n = Integer.parseInt(input.nextLine());String[] strs = input.nextLine().split(" ");int[] weights = new int[strs.length+1];int sum = 0;for (int i = 0; i < strs.length; i++) {weights[i+1] = Integer.parseInt(strs[i]);sum += weights[i];}if (sum % 2 == 1) {System.out.println(-1);return;}int target = sum / 2;int[][] dp = new int[n+1][target+1];for (int i = 0; i < dp.length; i++) {for (int j = 0; j < dp[0].length; j++) {dp[i][j] = Integer.MAX_VALUE/2;}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= target; j++) {if (j == weights[i]) {dp[i][j] = 1;} else if (j > weights[i]) {dp[i][j] = Math.min(dp[i][j], dp[i-1][j-weights[i]]+1);}}}System.out.println(dp[n][target]);}
}