1.描述
玩過三國殺的朋友應該都知道有個將叫張昌蒲，他會隨機給出N張卡牌，卡牌的點數在1-13之間，可能重復，現在要求把卡牌分為兩堆，兩邊卡牌的點數之和必須相等，要求兩堆的卡牌數之和盡量多，
針對這個邏輯，我自己寫了一些JAVA的實作，經過測驗可行，下面給出代碼，有興趣的朋友可以看看，有改進的地方歡迎指出！
2.代碼如下
計算分配方式的代碼：
1 public class CalculateCard { 2 3 public static void main(String[] args) { 4 Scanner scanner = new Scanner(System.in); 5 System.out.println("請輸入嚴教牌，按點數，以空格割開，如（13 11 10）："); 6 String input = scanner.nextLine(); 7 System.out.println(input); 8 String[] inputCards = input.split(" "); 9 List<Integer> list = new ArrayList<>(); 10 try { 11 Arrays.stream(inputCards).forEach(card -> list.add(Integer.parseInt(card))); 12 }catch (NumberFormatException e) { 13 System.out.println("請輸入數字，牌的點數在1-13"); 14 } 15 AtomicBoolean isCorrect = new AtomicBoolean(true); 16 list.forEach(item -> isCorrect.set(item <= 13 && item >= 1)); 17 if(!isCorrect.get()){ 18 System.out.println("----請輸入數字，牌的點數在1-13"); 19 } 20 calculateAll(list); 21 } 22 23 /** 24 * 計算所有可能的分配方式，并找到使用卡牌最多的組合方式 25 * @param list 所有輸入的數字 26 */ 27 private static void calculateAll(List<Integer> list){ 28 //存放所有的可行分配方式 29 List<Pair<Integer,Pair<String,String>>> okResult = new ArrayList<>(); 30 //存放使用牌數最多的分配方式 31 List<Pair<Integer,Pair<String,String>>> okResultLast = new ArrayList<>(); 32 //存放所有數字的組合 33 List<Pair<Integer,Pair<Integer,String>>> result = new ArrayList<>(); 34 //用于存放已經找到的分配方式，排除重復分配 35 List<String> listAdd = new ArrayList<>(); 36 //獲取所有的數字組合方式 37 getAllComb(list,result); 38 int countNum = 0; 39 //遍歷所有組合方式 40 for (int i = 0; i < result.size(); i++) { 41 /* 42 * 思路 43 * 1.取出其中一種組合，拿到這個組合的點數和sum 44 * 2.將當前組合中的所有數字放在一個List--currentList中 45 * 3.從原來得包含所有點數的卡牌集合中篩選出去掉currentList所有數字的其他數字，放在listLeft中 46 * 5.獲得listLeft中所有數字的全部組合方式，放在result1中 47 * 6.遍歷result1，比對總和與sum是否相等，相等則為一種成功的組合方式， 48 * 7.找到成功組合中使用卡牌最多的組合方式 49 */ 50 Pair<Integer,Pair<Integer,String>> pair = result.get(i); 51 int sum = pair.getValue().getKey(); 52 int numCount = pair.getKey(); 53 String com = pair.getValue().getValue(); 54 String[] numStr = com.split(","); 55 List<Integer> listLeft = new ArrayList<>(); 56 List<Integer> currentList = new ArrayList<>(); 57 for (int j = 0; j < numStr.length; j++) { 58 currentList.add(Integer.parseInt(numStr[j])); 59 } 60 for (int j = 0; j < list.size(); j++) { 61 if(!currentList.contains(list.get(j))) listLeft.add(list.get(j)); 62 } 63 List<Pair<Integer,Pair<Integer,String>>> result1 = new ArrayList<>(); 64 getAllComb(listLeft,result1); 65 for (int j = 0; j < result1.size(); j++) { 66 Pair<Integer,Pair<Integer,String>> pair1 = result1.get(j); 67 int leftSum = pair1.getValue().getKey(); 68 int leftCount = pair1.getKey(); 69 String com1 = pair1.getValue().getValue(); 70 countNum = countNum == 0 ? numCount + leftCount : countNum; 71 if(leftSum == sum && countNum <= numCount + leftCount){ 72 //計數，如果組合中的數字個數更大，則移除結果集，重新添加，只保存最多的 73 if(countNum != 0 && countNum < numCount+leftCount){ 74 countNum = numCount + leftCount; 75 okResultLast.clear(); 76 } 77 //去除牌堆左右互換的匹配組合 78 if(listAdd.contains(com1) || listAdd.contains(com)) continue; 79 listAdd.add(com1); 80 okResult.add(new Pair<>(numCount+leftCount,new Pair<>(com,com1))); 81 okResultLast.add(new Pair<>(numCount+leftCount,new Pair<>(com,com1))); 82 } 83 } 84 } 85 // System.out.println("所有組合："); 86 // for (int i = 0; i < okResult.size(); i++) { 87 // Pair<Integer,Pair<String,String>> resultPair = okResult.get(i); 88 // System.out.println("組合的總牌數："+resultPair.getKey() + 89 // " ===>組合1為： " + resultPair.getValue().getKey() + 90 // " ===>組合2為： " + resultPair.getValue().getValue()); 91 // } 92 System.out.println("================================================="); 93 System.out.println("使用卡牌最多的組合方式："); 94 System.out.println("================================================="); 95 for (int i = 0; i < okResultLast.size(); i++) { 96 Pair<Integer,Pair<String,String>> resultPair = okResultLast.get(i); 97 System.out.println("當前分配式方"+(i+1)+"總牌數："+resultPair.getKey() + 98 "\n====>堆一卡牌點數分別為： " + resultPair.getValue().getKey() + 99 "\n====>堆二卡牌點數分別為： " + resultPair.getValue().getValue()); 100 } 101 System.out.println("================================================="); 102 } 103 104 /** 105 * 獲得所有可能的組合 106 * 如數字串列為：【1,2,3】 107 * 那么得到的所有組合為【1】，【2】，【3】，【1,2】，【1,3】，【2,3】，【1,2,3】 108 * @param list 所有數字 109 * @param result 回傳的組合集合 110 */ 111 private static void getAllComb(List<Integer> list,List<Pair<Integer,Pair<Integer,String>>> result){ 112 List<String> com = new ArrayList<>(); 113 for (int i = 1; i != list.size() + 1; i++) { 114 ComputCombinations.getCombination(result,list,0,i,com); 115 } 116 // result.stream().forEach(item -> System.out.println("數字數："+ item.getKey()+ 117 // "=====>總值："+ item.getValue().getKey()+ " 內容：" + item.getValue().getValue())); 118 } 119 }
計算數字組合的演算法：
1 public static void getCombination(List<Pair<Integer,Pair<Integer,String>>> result, 2 List<Integer> list, int start, int len , List<String> com){ 3 if(len == 0){ 4 String s = ""; 5 for (int i = 0; i != com.size() ; i++) { 6 s = s.concat(com.get(i)); 7 } 8 String comStr = s.substring(0,s.length() - 1); 9 String[] all = comStr.split(","); 10 AtomicInteger sum = new AtomicInteger(); 11 Arrays.stream(all).forEach(item -> sum.addAndGet(Integer.parseInt(item))); 12 result.add(new Pair<>(com.size(),new Pair<>(sum.get(),comStr))); 13 return; 14 } 15 if(start == list.size()){ 16 return; 17 } 18 com.add(list.get(start)+","); 19 getCombination(result,list, start+1,len - 1,com); 20 com.remove(com.size()-1); 21 getCombination(result,list,start+1,len,com); 22 }
測驗結果：
有可以改進的地方，歡迎指出...
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/545098.html
標籤：其他