git地址flp19950214/optimal-elevator: 最优电梯组合方案模型package main.com.lift; import com.alibaba.fastjson.JSON; import com.google.common.collect.Lists; import com.google.common.collect.Maps; import org.junit.Test; import java.util.*; import java.util.concurrent.LinkedBlockingQueue; public class MatchTitle { //存放各种上楼方式组合、 public static ListListInteger makeupList Lists.newArrayList(); //存放每个人要去的楼层 public static ListInteger postionListLists.newArrayList(); //存放多人占坑方式组合 public static ListListListInteger zhankengListLists.newArrayList(); public static void main(String[] args) { int n3;//楼层数 int m4;//电梯数 int peopleNum100;//人数 ListListListInteger l1Lists.newArrayList(); for(int i1;in;i){ forTop(i);//到达顶层组合算法 l1.add(makeupList); } ListListInteger oneLiftCombinLists.newArrayList(); l1.forEach(item -{ oneLiftCombin.addAll(item); }); zhankeng(m,oneLiftCombin);//占坑组合 MapListListInteger,Double result Maps.newHashMap(); BaseDao baseDaonew BaseDao(); MatchTitle matchTitlenew MatchTitle(); LinkedBlockingQueueInteger queuematchTitle.peopleAndNumPosition(peopleNum,n);//生成等电梯的人的排队序列 for(int i0;izhankengList.size();i){ ListListInteger newljconvert(zhankengList.get(i));//将每次上的楼层个数改成楼层数 if(iscontainAllNum(newlj,n)){ //首先判断电梯组合是不是包含了所有楼层 continue; } //*********************************************执行每种电梯组合的运行时间********************************************** LinkedBlockingQueueInteger queue2new LinkedBlockingQueue();//生成等电梯的人的排队序列 queue2.addAll(queue); ExecuteRun executeRunnew ExecuteRun(); double resulttime0; try{ resulttimeexecuteRun.runanswer(newlj,queue2); }catch (Exception e){ e.printStackTrace(); } //一边循环一边保存 baseDao.save(newlj.toString(),resulttime); result.put(newlj,resulttime); System.gc(); } System.out.println(); result.forEach((k,v)-{ System.out.println(k : v); }); //根据value排序 MapListListInteger,Double resultSortsortMapByValue(result); System.out.println(resultSort.get(0)); }; Test public void alone(){ int peopleNum2000; int m26; MapListListInteger,Double resultMaps.newHashMap(); BaseDao baseDaonew BaseDao(); MatchTitle matchTitlenew MatchTitle(); LinkedBlockingQueueInteger queuematchTitle.peopleAndNumPosition(peopleNum,m);//生成等电梯的人的排队序列 String one[[1,3,5,7,9,11,13,15,17,19,21,23,25],[2,4,6,8,10,12,14,16,18,20,22,24,26]]; String two[[1,2,3,4,5,6,7,8,9,10,11,12,13],[14,15,16,17,18,19,20,21,22,23,24,25,26]]; List onelist JSON.parseArray(one); List twolistJSON.parseArray(two); ListListListInteger lTestLists.newArrayList(); lTest.add(onelist); lTest.add(twolist); for(int i0;ilTest.size();i){ ListListInteger newljlTest.get(i);//将每次上的楼层个数改成楼层数 if(!iscontainAllNum(newlj,m)){ //首先判断电梯组合是不是包含了所有楼层 continue; } //*****************************************执行每种电梯组合的运行时间****************************************** LinkedBlockingQueueInteger queue2new LinkedBlockingQueue();//生成等电梯的人的排队序列 queue2.addAll(queue); ExecuteRun executeRunnew ExecuteRun(); double resulttime0; try{ resulttimeexecuteRun.runanswer(newlj,queue2); }catch (Exception e){ e.printStackTrace(); } //一边循环一边保存 // baseDao.save(newlj.toString(),resulttime); result.put(newlj,resulttime); System.gc(); } System.out.println(); result.forEach((k,v)-{ System.out.println(k : v); }); //根据value排序 MapListListInteger,Double resultSortsortMapByValue(result); } /** * 从一次上一层楼两层三次n层一次迭代得出所有情况的由底层到达顶层的上电梯组合方式 * param n */ public static void forTop(int n){ for(int i1;in;i){ int numn-i; ListInteger listsLists.newArrayList(); lists.add(i); boolean flagtrue; if(num0){ flagfalse; forNotTop(num,lists); } if(flag)makeupList.add(lists); } } public static void forNotTop(int n,ListInteger lists){ ListInteger listLists.newArrayList(); list.addAll(lists); //循环本次余下楼层可能的组合方式 for(int i1;in;i){ int numn-i; lists.add(i); //flag是true的话说明刚好在本次循环的楼层中达到了顶层 boolean flagtrue; //num0 说明到达了顶层不要继续往下迭代 if(num0){ flagfalse; forNotTop(num,lists); } //体现flag的作用排除递归中的重复元素只把本次循环到达顶层的情况加入到总的list if(flag)makeupList.add(list); //使用存放的临时上级数据继续迭代本次循环的其他情况 listsLists.newArrayList(); lists.addAll(list); } } /** * 占坑组合 * param m * param lm */ public static void zhankeng(int m,ListListInteger lm){ int bm; for(int i0;ilm.size();i){ // m--表示当前的位置已定去掉只考虑其他的人 m--; ListListInteger listsLists.newArrayList(); lists.add(lm.get(i)); //当前的人所有情况是否完成 boolean flagtrue; //当前人与其他人的组合情况是否结束没有结束就进入到字方法中循环其他人的 if(m0){ flagfalse; zhankengson(m,lm,lists); } if(false)zhankengList.add(lists); mb; } } public static void zhankengson(int i,ListListInteger lm,ListListInteger lists){ //创建临时变量存储上次循环的情况以便于下一个的多有情况组合 ListListInteger listLists.newArrayList(); list.addAll(lists); int bi; for(int j0;jlm.size();j){ lists.add(lm.get(j)); i--; boolean flagtrue; if(i0){ flagfalse; zhankengson(i,lm,lists); } if(flag)zhankengList.add(lists); //使用存放的临时上级数据继续迭代本次循环的其他情况 listsLists.newArrayList(); lists.addAll(list); } } /** * //如将[[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4] * //改成[[1,2,,3,4],[1,2,4],[1,3,4],[1,4],[2,3,4],[2,4] * param l1 * return */ public static ListListInteger convert(ListListInteger l1){ ListListInteger resultlistLists.newArrayList(); for(int i0;il1.size();i){ ListInteger l2l1.get(i); ListInteger ltmpLists.newArrayList(); int tmp0; for(int j0;jl2.size();j){ ltmp.add(tmpl2.get(j)); tmpl2.get(j); } resultlist.add(ltmp); } return resultlist; } /** * 判断是否包含了所有楼层 * param produceElem * param n * return */ public static boolean iscontainAllNum(ListListInteger produceElem,int n){ ListInteger allNumLists.newArrayList(); for(ListInteger int1:produceElem){ for(Integer int2:int1){ allNum.add(int2); } } allNumLists.newArrayList(new TreeSetInteger(allNum)); if(allNum.size()n){ return false; } return true; } /** * 根据map的value排序 * param result * return */ public static MapListListInteger,Double sortMapByValue(MapListListInteger,Double result){ MapListListInteger,Double sortedMapMaps.newLinkedHashMap(); ListMap.EntryListListInteger,Double entryListLists.newArrayList(result.entrySet()); Collections.sort(entryList, new ComparatorMap.EntryListListInteger, Double() { Override public int compare(Map.EntryListListInteger, Double o1, Map.EntryListListInteger, Double o2) { return o1.getValue().compareTo(o2.getValue()); } }); IteratorMap.EntryListListInteger,Double iteratorentryList.iterator(); Map.EntryListListInteger,Double tmpEntrynull; while(iterator.hasNext()){ tmpEntryiterator.next(); sortedMap.put(tmpEntry.getKey(),tmpEntry.getValue()); } return sortedMap; } /** * 随机生成人的个数以及每个人所属的楼层 * param m * param n * return */ public LinkedBlockingQueueInteger peopleAndNumPosition(int m,int n){ LinkedBlockingQueueInteger queuenew LinkedBlockingQueue(); for( int i0;im;i){ queue.offer((int)(Math.random()*n)1); } return queue; } }pom.xml?xml version1.0 encodingUTF-8? project xmlnshttp://maven.apache.org/POM/4.0.0 xmlns:xsihttp://www.w3.org/2001/XMLSchema-instance xsi:schemaLocationhttp://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd modelVersion4.0.0/modelVersion groupIdcom.example/groupId artifactIdoptimal-elevator/artifactId version1.0-SNAPSHOT/version properties maven.compiler.source8/maven.compiler.source maven.compiler.target8/maven.compiler.target project.build.sourceEncodingUTF-8/project.build.sourceEncoding /properties dependencies dependency groupIdcom.alibaba.fastjson2/groupId artifactIdfastjson2/artifactId version2.0.43/version /dependency dependency groupIdcom.google.guava/groupId artifactIdguava/artifactId version32.1.3-jre/version /dependency dependency groupIdjunit/groupId artifactIdjunit/artifactId version4.13.2/version scopetest/scope /dependency /dependencies /project MatchTitle 主程序入口
git地址flp19950214/optimal-elevator: 最优电梯组合方案模型package main.com.lift; import com.alibaba.fastjson.JSON; import com.google.common.collect.Lists; import com.google.common.collect.Maps; import org.junit.Test; import java.util.*; import java.util.concurrent.LinkedBlockingQueue; public class MatchTitle { //存放各种上楼方式组合、 public static ListListInteger makeupList Lists.newArrayList(); //存放每个人要去的楼层 public static ListInteger postionListLists.newArrayList(); //存放多人占坑方式组合 public static ListListListInteger zhankengListLists.newArrayList(); public static void main(String[] args) { int n3;//楼层数 int m4;//电梯数 int peopleNum100;//人数 ListListListInteger l1Lists.newArrayList(); for(int i1;in;i){ forTop(i);//到达顶层组合算法 l1.add(makeupList); } ListListInteger oneLiftCombinLists.newArrayList(); l1.forEach(item -{ oneLiftCombin.addAll(item); }); zhankeng(m,oneLiftCombin);//占坑组合 MapListListInteger,Double result Maps.newHashMap(); BaseDao baseDaonew BaseDao(); MatchTitle matchTitlenew MatchTitle(); LinkedBlockingQueueInteger queuematchTitle.peopleAndNumPosition(peopleNum,n);//生成等电梯的人的排队序列 for(int i0;izhankengList.size();i){ ListListInteger newljconvert(zhankengList.get(i));//将每次上的楼层个数改成楼层数 if(iscontainAllNum(newlj,n)){ //首先判断电梯组合是不是包含了所有楼层 continue; } //*********************************************执行每种电梯组合的运行时间********************************************** LinkedBlockingQueueInteger queue2new LinkedBlockingQueue();//生成等电梯的人的排队序列 queue2.addAll(queue); ExecuteRun executeRunnew ExecuteRun(); double resulttime0; try{ resulttimeexecuteRun.runanswer(newlj,queue2); }catch (Exception e){ e.printStackTrace(); } //一边循环一边保存 baseDao.save(newlj.toString(),resulttime); result.put(newlj,resulttime); System.gc(); } System.out.println(); result.forEach((k,v)-{ System.out.println(k : v); }); //根据value排序 MapListListInteger,Double resultSortsortMapByValue(result); System.out.println(resultSort.get(0)); }; Test public void alone(){ int peopleNum2000; int m26; MapListListInteger,Double resultMaps.newHashMap(); BaseDao baseDaonew BaseDao(); MatchTitle matchTitlenew MatchTitle(); LinkedBlockingQueueInteger queuematchTitle.peopleAndNumPosition(peopleNum,m);//生成等电梯的人的排队序列 String one[[1,3,5,7,9,11,13,15,17,19,21,23,25],[2,4,6,8,10,12,14,16,18,20,22,24,26]]; String two[[1,2,3,4,5,6,7,8,9,10,11,12,13],[14,15,16,17,18,19,20,21,22,23,24,25,26]]; List onelist JSON.parseArray(one); List twolistJSON.parseArray(two); ListListListInteger lTestLists.newArrayList(); lTest.add(onelist); lTest.add(twolist); for(int i0;ilTest.size();i){ ListListInteger newljlTest.get(i);//将每次上的楼层个数改成楼层数 if(!iscontainAllNum(newlj,m)){ //首先判断电梯组合是不是包含了所有楼层 continue; } //*****************************************执行每种电梯组合的运行时间****************************************** LinkedBlockingQueueInteger queue2new LinkedBlockingQueue();//生成等电梯的人的排队序列 queue2.addAll(queue); ExecuteRun executeRunnew ExecuteRun(); double resulttime0; try{ resulttimeexecuteRun.runanswer(newlj,queue2); }catch (Exception e){ e.printStackTrace(); } //一边循环一边保存 // baseDao.save(newlj.toString(),resulttime); result.put(newlj,resulttime); System.gc(); } System.out.println(); result.forEach((k,v)-{ System.out.println(k : v); }); //根据value排序 MapListListInteger,Double resultSortsortMapByValue(result); } /** * 从一次上一层楼两层三次n层一次迭代得出所有情况的由底层到达顶层的上电梯组合方式 * param n */ public static void forTop(int n){ for(int i1;in;i){ int numn-i; ListInteger listsLists.newArrayList(); lists.add(i); boolean flagtrue; if(num0){ flagfalse; forNotTop(num,lists); } if(flag)makeupList.add(lists); } } public static void forNotTop(int n,ListInteger lists){ ListInteger listLists.newArrayList(); list.addAll(lists); //循环本次余下楼层可能的组合方式 for(int i1;in;i){ int numn-i; lists.add(i); //flag是true的话说明刚好在本次循环的楼层中达到了顶层 boolean flagtrue; //num0 说明到达了顶层不要继续往下迭代 if(num0){ flagfalse; forNotTop(num,lists); } //体现flag的作用排除递归中的重复元素只把本次循环到达顶层的情况加入到总的list if(flag)makeupList.add(list); //使用存放的临时上级数据继续迭代本次循环的其他情况 listsLists.newArrayList(); lists.addAll(list); } } /** * 占坑组合 * param m * param lm */ public static void zhankeng(int m,ListListInteger lm){ int bm; for(int i0;ilm.size();i){ // m--表示当前的位置已定去掉只考虑其他的人 m--; ListListInteger listsLists.newArrayList(); lists.add(lm.get(i)); //当前的人所有情况是否完成 boolean flagtrue; //当前人与其他人的组合情况是否结束没有结束就进入到字方法中循环其他人的 if(m0){ flagfalse; zhankengson(m,lm,lists); } if(false)zhankengList.add(lists); mb; } } public static void zhankengson(int i,ListListInteger lm,ListListInteger lists){ //创建临时变量存储上次循环的情况以便于下一个的多有情况组合 ListListInteger listLists.newArrayList(); list.addAll(lists); int bi; for(int j0;jlm.size();j){ lists.add(lm.get(j)); i--; boolean flagtrue; if(i0){ flagfalse; zhankengson(i,lm,lists); } if(flag)zhankengList.add(lists); //使用存放的临时上级数据继续迭代本次循环的其他情况 listsLists.newArrayList(); lists.addAll(list); } } /** * //如将[[1,1,1,1],[1,1,2],[1,2,1],[1,3],[2,1,1],[2,2],[3,1],[4] * //改成[[1,2,,3,4],[1,2,4],[1,3,4],[1,4],[2,3,4],[2,4] * param l1 * return */ public static ListListInteger convert(ListListInteger l1){ ListListInteger resultlistLists.newArrayList(); for(int i0;il1.size();i){ ListInteger l2l1.get(i); ListInteger ltmpLists.newArrayList(); int tmp0; for(int j0;jl2.size();j){ ltmp.add(tmpl2.get(j)); tmpl2.get(j); } resultlist.add(ltmp); } return resultlist; } /** * 判断是否包含了所有楼层 * param produceElem * param n * return */ public static boolean iscontainAllNum(ListListInteger produceElem,int n){ ListInteger allNumLists.newArrayList(); for(ListInteger int1:produceElem){ for(Integer int2:int1){ allNum.add(int2); } } allNumLists.newArrayList(new TreeSetInteger(allNum)); if(allNum.size()n){ return false; } return true; } /** * 根据map的value排序 * param result * return */ public static MapListListInteger,Double sortMapByValue(MapListListInteger,Double result){ MapListListInteger,Double sortedMapMaps.newLinkedHashMap(); ListMap.EntryListListInteger,Double entryListLists.newArrayList(result.entrySet()); Collections.sort(entryList, new ComparatorMap.EntryListListInteger, Double() { Override public int compare(Map.EntryListListInteger, Double o1, Map.EntryListListInteger, Double o2) { return o1.getValue().compareTo(o2.getValue()); } }); IteratorMap.EntryListListInteger,Double iteratorentryList.iterator(); Map.EntryListListInteger,Double tmpEntrynull; while(iterator.hasNext()){ tmpEntryiterator.next(); sortedMap.put(tmpEntry.getKey(),tmpEntry.getValue()); } return sortedMap; } /** * 随机生成人的个数以及每个人所属的楼层 * param m * param n * return */ public LinkedBlockingQueueInteger peopleAndNumPosition(int m,int n){ LinkedBlockingQueueInteger queuenew LinkedBlockingQueue(); for( int i0;im;i){ queue.offer((int)(Math.random()*n)1); } return queue; } }pom.xml?xml version1.0 encodingUTF-8? project xmlnshttp://maven.apache.org/POM/4.0.0 xmlns:xsihttp://www.w3.org/2001/XMLSchema-instance xsi:schemaLocationhttp://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd modelVersion4.0.0/modelVersion groupIdcom.example/groupId artifactIdoptimal-elevator/artifactId version1.0-SNAPSHOT/version properties maven.compiler.source8/maven.compiler.source maven.compiler.target8/maven.compiler.target project.build.sourceEncodingUTF-8/project.build.sourceEncoding /properties dependencies dependency groupIdcom.alibaba.fastjson2/groupId artifactIdfastjson2/artifactId version2.0.43/version /dependency dependency groupIdcom.google.guava/groupId artifactIdguava/artifactId version32.1.3-jre/version /dependency dependency groupIdjunit/groupId artifactIdjunit/artifactId version4.13.2/version scopetest/scope /dependency /dependencies /project