檢查數組中的總和Java

Question

我正在做一個名爲Thirty的骰子游戲，用Java編寫。我有一個像[1,3,4,5,5,6]這樣的骰子值的數組。從那個數組中，我希望能夠找到給定數量的每個組，但每個骰子只能計算一次。例如，如果我有數組[1,3,4,5,5,6]並且想要找到等於12的每個組，那麼這將給我例如1 + 5 + 6 = 12和3+ 4 + 5 = 12。

而且有一個像[1,1,1,1,2,6]這樣的例子，我會得到1 + 1 + 1 + 1 + 2 + 6 = 12。

總是會有6個骰子，但我正在尋找的總和可以是4和12

之間的任何一個人可以幫我嗎？我真的沒有任何代碼可以提供，只會令人困惑，根本沒有幫助。

Answer 1

我有一個算法可以解決你的問題，但你將不得不適應它的需要。 不幸的是，我不知道它是否是任何特定已知數據結構的一部分。

簡而言之，我會說它會將您的數組轉換爲二進制位置，並從中沒有任何項目被標記到所有標記的位置進行循環。

• 數組大小= 6
• 初始標記的陣列= 「000000」 // 6位未標記
• 最終被標記的陣列= 「111111」 // 6個位置標記

遞增二進制數組，它只是總結標記的位置。我們將能夠總結所有可能的組合。

TEST 1

鑑於你參數：

• 薩姆= 12
• 陣列= {1，3，4，5，5，6}

的結果是：

Position: 011010 // means the sum of item in position 1,2,4 (3 + 4 + 5 = 12) 
Position: 011100 // means the sum of item in position 1,2,3 (3 + 4 + 5 = 12) 
Position: 100011 // means the sum of item in position 0,4,5 (1 + 5 + 6 = 12) 
Position: 100101 // means the sum of item in position 0,3,5 (1 + 5 + 6 = 12) 

TEST 2

鑑於你參數：

• 薩姆= 12
• 陣列= {1，1，1，1，2，6}

結果是：

Position: 111111 // means the sum of item in position 0,1,2,3,4,5 (1+1+1+1+2+6 = 12) 

該代碼可以改進，bu t如下所示，簡單地將「1」打印到要求和的位置，即得到期望的數字。

public class Algorithm { 
 

 
public static void main(String[] args) { 
 
\t Algorithm checkSum = new Algorithm(); 
 

 
\t Integer[] array = {1, 3, 4, 5, 5, 6}; 
 
\t Integer sum = 12; 
 
\t checkSum.find(array, sum); 
 
\t 
 
\t System.out.println("------------------"); 
 
\t 
 
\t Integer[] array2 = {1, 1, 1, 1, 2, 6}; 
 
\t Integer sum2 = 12; 
 
\t checkSum.find(array2, sum2); 
 
} 
 

 
private void find(Integer[] array, Integer sum) { 
 
\t // This could be replaced by a StringUtils lib to fill with "1" the size of the array 
 
\t String maxBinary = ""; 
 
\t for (int i=0; i<array.length; i++) { 
 
\t \t maxBinary += "1"; 
 
\t } 
 
\t 
 
\t int maxDecimal = Integer.parseInt(maxBinary, 2); 
 
\t 
 
\t // This will iterate from "000000" to "111111" 
 
\t for (int i=0; i<=maxDecimal; i++) { 
 
\t \t String binaryNumber = lpad(Integer.toBinaryString(i), array.length); 
 
\t \t 
 
\t \t int checkSum = 0; 
 
\t \t for (int j=0; j<binaryNumber.length(); j++) { 
 
\t \t \t if ("1".equals(binaryNumber.substring(j,j+1))) { 
 
\t \t \t \t checkSum += array[j]; 
 
\t \t \t } 
 
\t \t } 
 
\t \t // This is the check to see if the sum is the desired one 
 
\t \t if (sum == checkSum) { 
 
\t \t \t System.out.println("Positions: " + binaryNumber); 
 
\t \t } \t 
 
\t } 
 
} 
 

 
/** 
 
* This is a simple LPAD function to add zeros to the left of the string. 
 
*/ 
 
private String lpad(String text, Integer size) { 
 
\t String regex = "%0"+ size + "d"; 
 
\t return String.format(regex, Integer.parseInt(text)); 
 
} 
 
}

希望它能幫助！

Answer 2

這裏沒有經過很好的測試，也許有點naiv的解決方案。我使用整數列表，因爲我不喜歡數組，對不起！

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.junit.Before; 
import org.junit.Test; 

public class PickNumbersTest { 

    private List<Integer> numbers; 

    @Before 
    public void before() { 
     Integer[] ints = new Integer[] { 1, 3, 4, 5, 5, 6 }; 
     numbers = new ArrayList<>(); 
     numbers.addAll(Arrays.asList(ints));   
    } 

    @Test 
    public void test() { 

     PickNumbers p = new PickNumbers(); 
     List<List<Integer>> result = p.pick(12, numbers); 

     System.out.println(result); 
    } 
} 

import java.util.ArrayList; 
import java.util.List; 

public class PickNumbers { 

    public List<List<Integer>> pick(final int sum, final List<Integer> values) { 

     // make a copy to avoid making changes to passed in List 
     List<Integer> numbers = copy(values); 

     List<List<Integer>> results = new ArrayList<List<Integer>>(); 

     while (!pickSingle(sum, numbers).isEmpty()) { 

      List<Integer> currentResult = pickSingle(sum, numbers); 

      results.add(currentResult); 
      currentResult.forEach(i -> numbers.remove(i)); 

     } 

     return results; 
    } 

    protected List<Integer> pickSingle(final int sum, final List<Integer> values) { 
     int rest = sum; 
     List<Integer> result = new ArrayList<>(); 
     Picker p = new Picker(values); 

     while (rest > 0 && p.hasNext()) { 

      int i = p.next(); 

      if (i > rest) { 
       p.remove(); 
      } else if (i == rest) { 
       result.add(i); 
       return result; 
      } else { // i < rest 
       result.add(i); 
       p.remove(); 
       rest = rest - i; 
      } 
     } 

     return new ArrayList<>(); 
    } 

    private List<Integer> copy(final List<Integer> values) { 

     List<Integer> copy = new ArrayList<Integer>(); 
     copy.addAll(values); 

     return copy; 
    } 
} 

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

public class Picker { 

    private List<Integer> values = new ArrayList<Integer>(); 

    public Picker(final List<Integer> values) { 

     this.values.addAll(values); 
     this.values.sort(null); 
     Collections.reverse(this.values); 
    } 

    public int next() { 

     return values.get(0); 
    } 

    public void remove() { 

     values.remove(0); 
    } 

    public boolean hasNext() { 

     return values.size() > 0; 
    } 
}