问题描述:
n 个人参加拔河比赛，每个人有自己的重量，现在需要把他们分成两组进行比赛，每个人属于其中的一个组，两组的人员个数相差不能超过1。为使比赛公平，求使得两组重量差最小的分配。
问题解决代码
package org.lulu.learn; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * Project: BaHeProblem * Created: Lulu * Date: 2016/8/15 */ public class Test { public static void main(String[] args) { try { System.setIn(new FileInputStream("res/input.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); } Scanner scanner = new Scanner(System.in); //获取到输入的总人数 int sum = scanner.nextInt(); //存放所有人的体重 ArrayList<Integer> list = new ArrayList<>(); //获取体重 for (int i = 0; i < sum; i++) { list.add(scanner.nextInt()); } int count = list.size() / 2;//队伍的人数(第一队) sum = 0; //体重全部相加之后, 求其平均值 for (Integer integer : list) { sum += integer; } int average = sum / 2; //新建第一队列表 ArrayList<Integer> first = new ArrayList<>(); //获取到 count个人与平均值的最小值 int func = func(list, count, average, first); System.out.println(func); System.out.println(first); list.removeAll(first); System.out.println(list); } public static int func(List<Integer> list, int count, int sum, List<Integer> first) { //当第一队的人数为count时, 结束递归 if (first.size() == count) { int firstSum = 0; for (Integer integer : first) { firstSum += integer; } return Math.abs(firstSum - sum); } else { int min = Integer.MAX_VALUE; List<Integer> minFirst = null; for (int i = 0; i < list.size(); i++) { ArrayList<Integer> listTemp = new ArrayList<>(list); ArrayList<Integer> firstTemp = new ArrayList<>(first); firstTemp.add(listTemp.remove(i)); int func = func(listTemp, count, sum, firstTemp); if (func < min) { min = func; minFirst = firstTemp; } } if(min == 0) { break; } first.clear(); first.addAll(minFirst); return min; } } }