检查数组中的总和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; 
    } 
}