添加数组数直到确定值

For an exercise, I have to add values of an array until a certain value is reached, showing all possible combinations.

对于练习，我必须添加数组的值，直到达到某个值，显示所有可能的组合。

Example: value = 4, array = {1, 2, 3}

示例:value = 4, array = {1,2,3}

Possible combinations are: 1+1+1+1, 1+1+2, 1+2+1, 1+3, 2+1+1, 2+2, 3+1

可能的组合是:1+1+1+1,1+1+2 +2,1+2+1,1+3,2+1+1,2+2,3+1

However, my code doesn't seem to work:

然而，我的代码似乎不能工作:

public static void main(String[] args) {

    double[] array = { 1., 2., 3. };
    double value = 4.;
    for (int i = 0; i < array.length; i++) {
        addNumber(array, value, i);
    }
}

public static void addNumber(double[] array, double value, int index) {

    double startNumber = array[index];
    double checkSum = 0;

    for (int i = 0; i < array.length; i++) {
        checkSum += array[i] + startNumber;
        if (checkSum == value){
        System.out.println(startNumber + " + " + array[i] + " = " + checkSum);
        } else if (checkSum < value){
            moreNumbers(array, value, checkSum);
        }
        checkSum = 0;
    }
}

public static void moreNumbers (double[] array, double value, double current){

    if (current == value){
        System.out.println(current);
    } else if (current < value) {

        for (int i = 0; i < array.length; i++){             
            current += array[i];
            System.out.println("+ " + array[i] + " = " + current);              
        }
        moreNumbers(array, value, current);
    }       
}

Output:

输出:

+ 1.0 = 3.0
+ 2.0 = 5.0
+ 3.0 = 8.0
+ 1.0 = 4.0
+ 2.0 = 6.0
+ 3.0 = 9.0
1.0 + 3.0 = 4.0
+ 1.0 = 4.0
+ 2.0 = 6.0
+ 3.0 = 9.0
2.0 + 2.0 = 4.0
3.0 + 1.0 = 4.0

I believe I'm having trouble finding the right algorithm, since I'm only getting some of the combinations, but not all.

我认为我很难找到正确的算法，因为我只得到了一些组合，但不是全部。

And there is my question: I'm looking for an algorithm that helps me understand this exercise and it's logic, not the final code.

我的问题是:我在寻找一种算法来帮助我理解这个练习，它是逻辑，而不是最终的代码。

EDIT: In further development of this exercise, I have to use numbers like 0.5 or 0.2 too, but the numbers are always positive, so this is another problem I'm hoping to find answers for.

编辑:在这个练习的进一步发展中，我也需要使用0.5或0.2这样的数字，但是数字总是积极的，所以这是另一个我希望能找到答案的问题。

3 个解决方案

#1

The general approach is:

一般的方法是:

1. Pick one of the available numbers, and see if that equals the target.
2. 选择一个可用的数字，看看它是否等于目标。
3. If not, you can pick any other number from the available numbers and add it to the previously picked number; again, check if you have reached the target.
4. 如果不是，您可以从可用的数字中选择任何其他数字并将其添加到先前选择的数字中;再次，检查你是否达到了目标。
5. Keep going until you have reached (or gone past) the target sum.
6. 一直走，直到你到达(或过去)目标和。

This can be implemented like this:

可以这样实施:

public static void startRecursion(int target, int[] numbers) {
  int min = numbers[0];
  for (int i = 1; i < numbers.length; ++i) {
    min = Math.min(min, numbers[i]);
  }
  // We need to choose at most ceil(target / min) numbers.
  int maxPicks = (target + min - 1) / min;
  recurse(new int[maxPicks], 0, 0, target, numbers);
}

private static void recurse(
    int[] picked, int numPicked, int sumOfPicked,
    int target, int[] numbers) {
  if (sumOfPicked == target) {
    // We reached the target! Print out the numbers we chose to get here.
    for (int i = 0; i < numPicked; ++i) {
      if (i != 0) System.out.print(" + ");
      System.out.print(picked[i]);
    }
    System.out.println(" = " + target);
  } else if (sumOfPicked < target) {
    // We haven't reached the target yet.
    // Go through each of the numbers that you can choose from numbers
    // in turn, increasing the sum by this amount.
    for (int i = 0; i < numbers.length; ++i) {
      picked[numPicked] = numbers[i];
      recurse(
          picked, numPicked + 1, sumOfPicked + numbers[i],
          target, numbers);
    }
  } else {
    // We have overshot the target. Since no numbers are negative,
    // we can't get back to the target again.
  }
}

#2

This seems to be solvable easily with recursion, like this :

这似乎很容易用递归解决，比如:

Getting the solution for 4 and {1,2,3} (written below as solution(4, {1,2,3}) is like getting the solution for

获取4和{1,2,3}的解决方案(在下面作为解决方案(4，{1,2,3})就像获取解决方案一样

• "1 + " + solution(3, {1, 2, 3})
• “1 +”+溶液(3，{1,2,3})
• "2 + " + solution(2, {1, 2, 3})
• “2 +”+溶液(2，{1,2,3})
• "3 + " + solution(1, {1, 2, 3})
• “3 +”+解决方案(1，{1,2,3})

At each step, you decrease the number (if there is not 0 in the list of available numbers, of course), so you are sure that the recursion will finish.

在每一步中，您都要减少数字(当然，如果可用数字列表中没有0)，因此您确信递归将完成。

You can have two outcome :

你可以有两个结果:

• no possibility (like you need to produce 1, but there is not 1 in the list of available numbers)
• 不可能(就像你需要生产1，但是在可用的数字列表中没有1)
• 1 or more potential solutions
• 一个或多个潜在的解决方案

There is another thing to pay attention to : floating point equality. == will not work everytime.

还有一件事需要注意:浮点等式。例:i will not work everytime。

the code would like like :

守则如下:

public static void main(String[] args) {
    ArrayList<String> solutions = new ArrayList<String>();
    solve("", 1.0d, new Double[] {0.2d, 0.50d}, solutions);
    System.out.println(solutions);
    // [0.2 + 0.2 + 0.2 + 0.2 + 0.2, 0.5 + 0.5]
    solutions.clear();
    solve("", 4d, new Double[] {1d, 2d, 3d}, solutions);
    System.out.println(solutions);
    // [1.0 + 1.0 + 1.0 + 1.0, 1.0 + 1.0 + 2.0, 1.0 + 2.0 + 1.0, 1.0 + 3.0, 2.0 + 1.0 + 1.0, 2.0 + 2.0, 3.0 + 1.0]
}

public static void solve(String subSolution, Double remaining, Double[] authorizedNumbers, List<String> solutions) {
    if (doubleEquals(remaining, 0d)) {
        solutions.add(subSolution);
    } else {
        for(Double authorizedNumber : authorizedNumbers) {
            if (doubleEquals(authorizedNumber, remaining)) {
                solutions.add(subSolution + authorizedNumber);
            } else if (authorizedNumber < remaining) {
                solve(subSolution + authorizedNumber + " + ", remaining - authorizedNumber, authorizedNumbers, solutions);
            }
        }
    }
}

public static boolean doubleEquals(double d1, double d2) {
    return Math.abs(d1 - d2) < 0.000000001d;
}

#3

Here is one of the solutions based on Combination Technique.

这是一种基于组合技术的解决方案。

Algorithm:

算法:

1. Compute all the combination (with repetition) from length {input} to 1.
2. 计算从长度{input}到1的所有组合(包括重复)。
3. Print only those combinations which satisfy the sum condition.
4. 只打印那些满足和条件的组合。

For Example, if input is 4 then some of the different combinations of length = 4 will be as follows:

例如，如果输入是4，那么长度= 4的一些不同组合如下:

1 1 1 1
1 1 1 2
.
.
2 1 2 3
.
.
3 3 3 3

Now, we'll only print 1 1 1 1 since it sums up to input i.e. 4 and satisfies the condition.

现在，我们只打印11,1因为它和输入相加，也就是4，满足条件。

Similarly, for length = 3 some of the different combinations will be as follows:

同样，对于长度= 3，一些不同的组合如下:

1 1 1
1 1 2
.
.
1 2 1
.
.
3 3 3

Now, we'll only print 1 1 2, 1 2 1 and 2 1 1 since they all satisfy the sum condition.

现在，我们只打印1 1 2 1 2 1和2 1因为它们都满足求和条件。

Here is a brief description of how different combinations are computed:

下面简要介绍不同的组合是如何计算的:

1. Combination function checks for the last element of the array and increments it if it is not MAX and branches the function.
2. 组合函数检查数组的最后一个元素，如果不是MAX，则递增，并对函数进行分支。
3. If the last element is max then we scan through the array for next number that is not MAX.
4. 如果最后一个元素是max，那么我们可以通过数组来查找下一个不是max的数字。
5. If the above scan fails as the array is exhausted then we return the flow to our main function but, if the scan return a position which is not max then we increment the value at that position by 1 and reset all the values after that position to MIN. We again branches the function.
6. 如果上述扫描失败作为数组疲惫然后我们返回流的主要功能,但如果扫描返回的位置不是马克斯然后增量的值在这个位置1和重置后的所有值最小。我们再次分支函数。

(It computes all the combinations for a given length using recursion)

(使用递归计算给定长度的所有组合)

Code Snippet:

代码片段:

class Combinations
{
    /* Constants Array (Sorted) */
    private static final double[] ARR_CNST = {0.1,0.2,0.3};
    /* Size of Constant Array */
    private static final int SIZE = 3;

    public static void main (String[] args)
    {
        /* Input Number */
        double input = 0.4;
        /* Start Permutations {Length --> 1} */
        for(int i = (int) (input/ARR_CNST[0]); i > 0; i--) {
            double[] storage = new double[i];
            /* Fill Array With Least Element */
            Arrays.fill(storage,ARR_CNST[0]);
            /* Check Sum Condition */
            if(check(storage,input)) {
                /* Print */
                print(storage);
            }
            /* Calculate Rest of the Combinations */
            calc(storage, input);
        }
    }

    private static void calc(double[] arr, double input) {
        /* Increment Last Element if not MAX */
        if(arr[arr.length - 1] < ARR_CNST[SIZE - 1]) {
            int k = 0;
            while(k < SIZE && arr[arr.length - 1] != ARR_CNST[k++]);
            arr[arr.length - 1] = ARR_CNST[k];
            if(check(arr,input)) {
                print(arr);
            }
            calc(arr, input);
        }

        /* Increment & Reset */
        int i = arr.length - 1;
        while(i >= 0 && arr[i] >= ARR_CNST[SIZE - 1])
            i--;

        if(i >= 0) {
            int k = 0;
            while(k < SIZE && arr[i] != ARR_CNST[k++]);
            arr[i] = ARR_CNST[k];

            for(int x = i + 1; x < arr.length; x++) {
                arr[x] = ARR_CNST[0];
            }

            if(check(arr,input)) {
                print(arr);
            }
            calc(arr, input);
        }

        /* Return */
        return;
    }

    /* Check Sum Condition */
    private static boolean check(double[] arr, double input) {
        double sum = 0;
        for(int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        if(sum == input) {
            return true;
        }
        return false;
    }

    /* Print Array Values */
    private static void print(double[] arr) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < arr.length; i++) {
            sb.append(arr[i] + " + ");
        }
        System.out.println(sb.substring(0,sb.length() - 3));
    }
}

Output:

输出:

0.1 + 0.1 + 0.1 + 0.1
0.1 + 0.1 + 0.2
0.1 + 0.2 + 0.1
0.2 + 0.1 + 0.1
0.1 + 0.3
0.2 + 0.2
0.3 + 0.1