拔河问题 java 回溯法

问题描述:

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(); //存放所有人的体重

ArrayListlist=new ArrayList<>(); //获取体重

for(int i=0;iint count=list.size()/2;//队伍的人数(第一队) sum=0;

//体重全部相加之后,求其平均值 for(Integer integer:list){ sum+=integer; }

int average=sum/2; //新建第一队列表

ArrayListfirst=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(Listlist,int count,int sum,Listfirst){

//当第一队的人数为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; ListminFirst=null; for(int i=0;iArrayListlistTemp=new ArrayList<>(list); ArrayListfirstTemp=new ArrayList<>(first); firstTemp.add(listTemp.remove(i));

int func=func(listTemp,count,sum,firstTemp); if(funcminFirst=firstTemp; } }

if(min==0){ break; }

first.clear();

first.addAll(minFirst); return min; } } }