【算法学习】基于“平均”的随机分配算法（贪婪，回溯），以按平均工作量随机分配单位为例
一、背景介绍
在工作中，遇到一个需求：将 N 个单位随机分配给 n 个人，其中每个单位有对应的工作量，分配时要尽量按工作量平均分给 n 个人，且人员的所属单位不能包括在被分配的单位中（N >= n）。例如：有三个部门分给两个人([A]属于部门2和[B]属于部门3)，部门1的工作量是999，部门2是2，部门3是4，这样分配结果为 A分配部门3或部门1和部门3，B分配部门1和部门2或部门2。
二、算法思路
刚开始的时候想不明白怎么让它们分配的“平均”，后面在网上找了找资料，于是面对这个需求我的大体算法思路是： 1. 采用贪婪算法将 N 个单位按照工作量进行分组； 1.1 对单位按工作量大小进行倒序排序； 1.2 首次分组时将最大工作量的 n 个先分组； 1.3 判断是否有剩余，n * i <= N?（i：分的次数），条件成立就执行 1.4，条件不成立就执行 1.5，一直循环直到所有单位分完； 1.4 接着第二次分组时找到分组的总工作量最小的，将单位分给总工作量最小的组； 1.5 将剩余数量 N%n 个单位分配完。 2. 采用回溯算法的思想将分组进行随机分配给 n 个人。 2.1 循环对 n 个人进行分配，同时在分配时判定条件 2.2 、2.3 和 2.4，如果全部符合且每个人都分配完成，则分配完成。 2.2 判断随机出来的分组是否已分配，是：重新分配，否：继续下一步； 2.3 判断随机出来的分组中单位是否包含了待分配人员的所属单位，是：重新分配，否：继续下一步； 2.4 判断随机了全部分组是否不能满足 2.1 和 2.2 的条件，是：重新分配，否：继续下一步；
三、源代码
主程序
package com.select;
import java.util.ArrayList;
import java.util.List;
/**
* 主函数
* @author 欧阳
* @since 2018年11月7日
*/
public class SelectMain {
/**
* 需求：将N个单位按工作量多少“尽量平均”分配给n个人，且所属单位不能在分配的部门中，并且不论怎么样都必须有分配结果。
* 例如：有三个部门分给两个人(属于[A]部门2和[B]部门3)，部门1的工作量是999，部门2是2，部门3是4，
* 这样分配结果为 A分配部门3或部门1和部门3，B分配部门1和部门2或部门2
* @param args
*/
public static void main(String[] args) {
run();
}
public static void run() {
//1.初始化部门，人员数据
List
List
//2.对部门进行从大到小排序
departments = SelectUtil.sortDesc(departments);
//3.获取人员所属部门数据
List
for(Person person : persons) {
personDepts.add(person.getDeptNo());
}
//4.按照工作量进行分组
List
//5.将分组结果随机分配给每个人
results = SelectUtil.distribute(results, persons);
System.out.println("+++++++++++ 部门信息 +++++++++++");
Long workLoad = SelectUtil.workLoad(departments);
System.out.println("总工作量：" + workLoad);
System.out.println("平均工作量：" + workLoad/persons.size());
//6.在控制台打印出分配结果
SelectUtil.print(results, persons);
}
}
工具类
package com.select;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Scanner;
/**
* 描述：工具类
* @author 欧阳
* @since 2018年11月7日
* @version 1.0
*/
public class SelectUtil {
/**
* 描述：按照工作量进行分组
* @param departments 部门数据
* @param personDepts 人员所属部门
* @return results 分组结果
* @author 欧阳荣涛
* @since 2018年11月6号
*/
public static List
List
Result result = new Result(); //记录分组结果
int deptNum = departments.size(); //部门数量
int personNum = personDepts.size(); //人员数量
int num = deptNum / personNum; //分组次数
if(personNum % deptNum != 0) {
num = num + 1;
}
//开始分组
int k = 0; //记录下一个分组的部门，从0开始
for(int i=1; i<=num; i++) {
if(i == 1) {
//首次分组,分人员数量的组
for(int j=0; j Department department = departments.get(k); result.addGroup(j, department); k++; // System.out.println(result.toString()); // System.out.println("下一个分组部门是：" + k); } } else { //分第二次到最后 /* * 贪婪，优先分给总工作量最小的 */ if(personNum * i <= deptNum) { for(int j=0; j Department department = departments.get(k); Integer groupNo = findGroupMinLoad(result, personDepts, department); // System.out.println("找到最小工作量组：" + groupNo); result.addGroup(groupNo, department); k++; // System.out.println(result.toString()); // System.out.println("下一个分组部门是：" + k); } } else { //如果有剩余，分最后剩余的 for(int j=0; j Department department = departments.get(k); Integer groupNo = findGroupMinLoad(result, personDepts, department); // System.out.println("找到最小工作量组：" + groupNo); result.addGroup(groupNo, department); k++; // System.out.println(result.toString()); // System.out.println("下一个分组部门是：" + k); } } } } if(k == departments.size()) { results.add(result); } else { System.out.println("分组失败！"); } return results; } /** * 描述：将分组结果随机分给每个人，所属单位不能包含在分组中 * @param results 分组结果（没有分配结果） * @param persons 人员信息 * @return results 分配结果 * @author 欧阳荣涛 * @since 2018年11月6号 */ public static List int number = persons.size(); //人员数量 int time = 0; //记录分配次数 for(Result result : results) { Boolean flag = false; //分配成功标志。默认是没分配成功：false Map Map List while(!flag) { //随机分配给每个人（回溯，只有分配条件成立才完成分配） System.out.println("正在随机分配各组......"); time++; //分配次数加1 usedNum.clear(); for(Person person : persons) { conDept.clear(); //随机生成组 int random = new Random().nextInt(number); //随机数范围：0<=random System.out.println("产生随机数【" + random + "】"); System.out.println("尝试将第【" + random + "】组进行分配......"); //判断是否已经分配了，已经分配了就不能在分 if(usedNum.containsKey(random)) { System.out.println("第【" + random + "】组已分配，将重新分配......"); break; } //判断分组是否包含所属单位，包含就不能分 List Integer deptNo = person.getDeptNo(); //所属单位 for(Department department : departments) { conDept.add(department.getDeptNo()); } if(conDept.contains(deptNo)) { System.out.println("第" + random + "组中包含所属单位【" + deptNo + "】，将重新分配......"); break; } //判断是否全部分配了也没有找到分配结果需要重新分配 if(usedNum.size() == number) { System.out.println("分配方式出现问题，将重新分配......"); break; } //存储已经分配的分组 usedNum.put(random, random); //分配分组 result.getToPerson().put(person.getPersonNo(), random); System.out.println("尝试将第【" + random + "】组分配给【" + person.getName() + "】..."); } //分配成功，设置标志，退出循环 if(usedNum.size() == number) { flag = true; break; } System.out.println("分配方案有误，准备重新分配......"); } //分配成功，退出循环 if(flag) { System.out.println("【完成分配】，共分配【" + time + "】次"); break; } } return results; } /** * 描述：输出分配结果 * @param results 分配结果 * @param persons 人员信息 * @author 欧阳荣涛 * @since 2018年11月6号 */ public static void print(List for(Result result : results) { Map Map Map System.out.println("+++++++++++ 分配结果 +++++++++++"); for(Integer personNo : toPerson.keySet()) { System.out.println("============================="); //查找人员信息 String personName = ""; //姓名 Integer deptNo = 0; //所属部门 for(Person person : persons) { if(person.getPersonNo().equals(personNo)) { personName = person.getName(); deptNo = person.getDeptNo(); } } Integer groupNo = toPerson.get(personNo); System.out.println("【" + personName + "】，" + "所属部门：【 " + deptNo + "】，" + "分配第【" + groupNo + "】组，" + "包括有："); for(Department department: result2.get(groupNo)) { System.out.println(department.getName() + "(" + department.getDeptNo() + ")" + "，工作量：" + department.getWorkLoad()); } System.out.println("总工作量：" + totalWorkLoad.get(groupNo)); } } } /** * 描述：找到分组中哪个分组的总的工作量最少 * @param result 分组结果 * @param personDepts 人员所属部门 * @param department 待分组的部门 * @author 欧阳荣涛 * @return groupNo 工作量最小的分组的序号，如果每个人的所属部门在同一组中返回倒数第二小的组 * @since 2018年11月7号 */ public static Integer findGroupMinLoad(Result result, List Department department) { Integer groupNo = 0; //默认最小的分组的序号为 0 Integer groupNoPre = 0; //记录上一次最小的分组，默认为 0 Long minLoad = 99999L; //最小工作量，默认99999 //找最小工作量的组 Map for(Integer key : totalWorkLoad.keySet()) { Long value = totalWorkLoad.get(key); if(value < minLoad) { minLoad = value; groupNo = key; } } //找最倒数第二小的组 Long poor = 99999L; //与最小工作量的差 for(Integer key : totalWorkLoad.keySet()) { Long value = totalWorkLoad.get(key); Long temp = Math.abs(value - minLoad); if(poor > temp && temp != 0) { groupNoPre = key; } } /* * 判断最小分组中有多少个包含人员的所属部门 */ Map List int num = 0; //记录分了几个所属部门在最小组 //1.先找出最小组中有几个 for(Department dept : list) { if(personDepts.contains(dept.getDeptNo())) { num++; } } //2.再找待分组的部门是否也包含其中 if(personDepts.contains(department.getDeptNo())) { num++; } /* * 将要分组的部门如果分入最小组则会导致整组包含所有所属部门，将不能分配， * 则将将要分组的部门分到倒数第二小组 */ if(num == personDepts.size()) { return groupNoPre; } return groupNo; } /** * 描述：将部门倒叙排序,并返回倒序结果 * @param departments 所有带有工作量的部门 * @return departments 倒序后的结果 * @author 欧阳荣涛 * @since 2018年11月7号 */ public static List Collections.sort(departments, new Comparator @Override public int compare(Department o1, Department o2) { if(o1.getWorkLoad() > o2.getWorkLoad()) { return -1; } else if(o1.getWorkLoad() == o2.getWorkLoad()) { return 0; } return 1; } }); return departments; } /** * 描述：计算总工作量 * @param departments 部门信息 * @return total 总工作量 * @author 欧阳荣涛 * @since 2018年11月7号 */ public static Long workLoad(List Long total = 0L; for(Department department : departments) { total += department.getWorkLoad(); } return total; } /** * 描述：退出 * @author 欧阳 * @since 2018年11月7日 */ public static void exit() { Scanner sc = new Scanner(System.in); while(true) { System.out.println("按“0”退出程序"); String print = sc.next(); if("0".equals(print)) { sc.close(); break; } } System.exit(-1); } /** * 描述：初始化部门信息 * @author 欧阳荣涛 * @since 2018年11月7日 */ public static List List //初始化部门 Department d1 = new Department(1, "市场部", 999L); Department d2 = new Department(2, "产品部", 18L); Department d3 = new Department(3, "开发部", 17L); Department d4 = new Department(4, "财物部", 16L); Department d5 = new Department(5, "项目部", 12L); Department d6 = new Department(6, "客服部", 14L); Department d7 = new Department(7, "运维部", 15L); departments.add(d1); departments.add(d2); departments.add(d3); departments.add(d4); departments.add(d5); departments.add(d6); departments.add(d7); return departments; } /** * 描述：初始化人员信息 * @author 欧阳荣涛 * @since 2018年11月7日 */ public static List List //初始化人员 Person p1 = new Person(1,"张三", 3); Person p2 = new Person(2,"李四", 4); Person p3 = new Person(3,"王五", 5); persons.add(p1); persons.add(p2); persons.add(p3); return persons; } } 将部门、人员和分组结果封装成实体： 在分组结果实体中有个将部门添加到分组中,同时计算分组的总工作量的方法； package com.select; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 描述：结果实体，用来存放分组结果 * @author 欧阳 * @since 2018年11月07日 * @version 1.0 */ public class Result { private Map private Map private Map public Result() { super(); result = new HashMap<>(); totalWorkLoad = new HashMap<>(); toPerson = new HashMap<>(); } /** * 描述：将部门添加到分组中,同时计算分组的总工作量 * @param groupNo 添加的目标组号 * @param department 添加的目标部门 */ public void addGroup(int groupNo, Department department) { List if(list == null) { list = new ArrayList<>(); } //将新加的部门添加到分组 list.add(department); result.put(groupNo, list); //计算分组的总工作量 Long total = totalWorkLoad.get(groupNo); if(total == null) { totalWorkLoad.put(groupNo, department.getWorkLoad()); } else { totalWorkLoad.put(groupNo, total+department.getWorkLoad()); } } public Map return result; } public Map return totalWorkLoad; } public Map return toPerson; } @Override public String toString() { return "Result [result=" + result + ", totalWorkLoad=" + totalWorkLoad + ", toPerson=" + toPerson + "]"; } } 部门实体： package com.select; /** * 描述：部门实体，用来存放部门 * @author 欧阳 * @since 2018年11月07日 * @version 1.0 */ public class Department { private Integer deptNo; //部门号 private String name; //部门名称 private Long workLoad; //工作量 public Department(Integer deptNo, String name, Long workLoad) { super(); this.deptNo = deptNo; this.name = name; this.workLoad = workLoad; } public Integer getDeptNo() { return deptNo; } public void setDeptNo(Integer deptNo) { this.deptNo = deptNo; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Long getWorkLoad() { return workLoad; } public void setWorkLoad(Long workLoad) { this.workLoad = workLoad; } @Override public String toString() { return "Department [deptNo=" + deptNo + ", name=" + name + ", workLoad=" + workLoad + "]"; } } 人员实体： package com.select; /** * 描述：人员实体，用来存放人员 * @author 欧阳 * @since 2018年11月07日 * @version 1.0 */ public class Person { private Integer personNo; //人员编号 private String name; //人员姓名 private Integer deptNo; //所属部门 public Person(Integer personNo, String name, Integer deptNo) { super(); this.personNo = personNo; this.name = name; this.deptNo = deptNo; } public Integer getPersonNo() { return personNo; } public void setPersonNo(Integer personNo) { this.personNo = personNo; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Integer getDeptNo() { return deptNo; } public void setDeptNo(Integer deptNo) { this.deptNo = deptNo; } @Override public String toString() { return "Person [personNo=" + personNo + ", name=" + name + ", deptNo=" + deptNo + "]"; } } 四、遗留问题 1. 坐观整个算法，在分组时没有考虑到多个分组结果，在最后的分组结果中还可以继续对分组结果进行分配上的优化；希望有兴趣的你给些宝贵意见和建议。 2. 在时间复杂度上感觉有点复杂。
