查找數組中的所有組合

Question

我正在使用Java在Android Studio中開發遊戲，並且對計數得分的方法有些麻煩。基本上在遊戲中，我有一組數值從1到6的骰子。在這些值中，我需要找出特殊值出現的次數。

現在我有這使得它尋找所有的單值做工精細的方法（如具有的值的所有骰子5），並且還如果兩個骰子加起來特殊值（如2 + 3或1 + 4）。但是，當有多於兩個骰子加起來的數字（如1 + 1 + 3）時，它沒有找到特殊值。

例如：如果我有骰子值爲[1,2,2,2， 3，5] 結果應該是三個「numberOfPairs」（1 + 2 + 2，2 + 3，5），因此方法應該返回15，但對於我來說它只返回10。一些想法如何改變這種方法更好地工作。

這裏是我一直在工作的方法：

public static int evaluatePoints(Dice dices[], int sumToReach) { 
    int values[] = new int[dices.length]; 
    int numberOfPairs = 0; 
    int left = 0; 
    int right = values.length - 1; 

    for(int i = 0; i < dices.length; i++){ 
      values[i] = dices[i].getValue(); 
      if(values[i] == sumToReach){ 
       numberOfPairs++; 
       values[i] = 0; 
      } 

    } 

    Arrays.sort(values); 

    while (values[right] > sumToReach + values[0]) { 
     right--; 
    } 

    while (left < right) { 
     if (values[left] + values[right] == sumToReach) { 
      numberOfPairs++; 
      left++; 
      right--; 
     } 
     else if(values[left] + values[right] < sumToReach) { 
      left++; 
     } 
     else right--; 
    } 
    return numberOfPairs*sumToReach; 
} 

Answer 1

你的問題可以解釋爲「把所有可能的多次交涉其他自然數的總和」。 Here是相當不錯的解決方案。

Answer 2

算法的說明：

Suppose the input array is [1 2 2 2 3 5] 

First the program will search for grpSize 6 i.e. 6 elements that sum upto sum of 5 
Then the program will search for grpSize 5 i.e. 5 elements that sum upto sum of 5 
. 
. 
. 
then the program will search for grpSize 1 i.e. 1 element that sums upto sum of 5 

If a set is found then elements will be removed from the resultList 

Warning: This approach is recursive, may lead to stack overflow if number of dice increases manyfold 

---

public static boolean func(int grpSize,int sum,int index,List<Integer> resultList,ArrayList<Integer> values) { 
    if(grpSize==1) { 
     int j; 
     for(j = index; j < resultList.size(); j++) { 
      if(resultList.get(j) == sum) { 
       values.add(resultList.get(j)); 
       resultList.remove(j); 
       return true; 
      } 
     } 
    } 

    for(; index < resultList.size(); index++) { 
     if(func(grpSize-1, sum-resultList.get(index), index+1, resultList, values)) { 
      values.add(resultList.get(index)); 
      resultList.remove(index); 
      return true; 
     } 
    } 
    return false; 
} 


public static void main(String[] args) { 
    List<Integer> resultList = new ArrayList<>(); 
    ArrayList<ArrayList<Integer>> values = new ArrayList<>(); 

    resultList.add(1); 
    resultList.add(2); 
    resultList.add(2); 
    resultList.add(2); 
    resultList.add(3); 
    resultList.add(5); 
    //3 2 2 2 3 5 

    int sum = 5;  
    int n = resultList.size(); 

    for(int i = 0; i < n; i++) { 
     int k=i; 
     while(true) { 
      values.add(new ArrayList<>()); 
      func(n-i, sum, 0, resultList, values.get(values.size() - 1)); 
       if(values.get(k).isEmpty()) { 
        break; 
       } else { 
        k++; 
       } 
      } 
     } 

     values.removeIf(p -> p.isEmpty()); 

     System.out.println("Number of pairs: "+values.size()); 

     values.forEach((it) -> { 
      System.out.println(it); 
     }); 

     int temp = 0; 

     for(int i = 0; i < values.size(); i++) { 
      for(int j = 0; j < values.get(i).size(); j++) { 
       temp += values.get(i).get(j); 
      } 
     } 
     System.out.println("sum: "+temp); 
    } 
} 

遞歸函數的工作：

此功能需要

• 組大小來搜索
• 總和搜索
• 開始索引這始終是零（可以（應該）被清理）
• 每個列表的擲骰
• 的方式來加入找到的值

這是一個布爾函數，如果發現某個特定集合加起來就會返回true。概念是基本的Backtracking