Coin Separation Algorithm

Question

My question is about the CodeFu practice problem (problem 3 rounds 2 rounds). Basically it comes down to splitting the array of integers into two (almost) equal halves and returning the smallest possible difference between them. I have included a description of the problem below. As noted in the comments, this can be described as a problem of a balanced section , which is a problem in the field of dynamic programming .

Now similar problems have been discussed a lot, but I could not find an effective solution for this particular one. The problem, of course, is that the number of possible combinations for moving in the near future is too large to search for brute force (at least when using recursion). I have a recursive solution that works great for everyone except the largest task sets. I tried to add some optimizations that stop recursion earlier, but the performance is still too slow to solve some arrays of maximum length (30) within the 5 second maximum allowed by CodeFu. Any suggestions on how to improve or rewrite the code would be very welcome. I would also like to know if the iterative version can do this.

Update: on this wonderful site there is a theoretical discussion of the problem of a balanced partition, which gives a good idea on how to do this and solve it dynamically. This is what I do, but I don’t know how to apply the theory correctly. The film mentions that elements in two subcollections can be found "using the old backtick trick", but I don’t see how.

Problem

You and your friend have several coins with different amounts. You need to divide the coins into two groups so that the difference between these groups is minimal.

eg. Coins of sizes 1,1,1,3,5,10,18 can be divided as: 1,1,1,3,5 and 10,18 1,1,1,3,5,10 and 18 or 1,1, 3,5,10 and 1,18 The third combination is favorable, since in this case the difference between the groups is only 1. Restrictions: coins will have from 2 to 30 elements, including each element of coins, will be between 1 and 100000 inclusive

Return value: the minimum difference is possible when the coins are divided into two groups

NOTE. The CodeFu rules state that the runtime on the CodeFu server can be no more than 5 seconds.

Main code

Arrays.sort(coins); lower = Arrays.copyOfRange(coins, 0,coins.length-1); //(after sorting) put the largest element in upper upper = Arrays.copyOfRange(coins, coins.length-1,coins.length); smallestDifference = Math.abs(arraySum(upper) - arraySum(lower)); return findSmallestDifference(lower, upper, arraySum(lower), arraySum(upper), smallestDifference); 

Recursion code

 private int findSmallestDifference (int[] lower, int[] upper, int lowerSum, int upperSum, int smallestDifference) { int[] newUpper = null, newLower = null; int currentDifference = Math.abs(upperSum-lowerSum); if (currentDifference < smallestDifference) { smallestDifference = currentDifference; } if (lowerSum < upperSum || lower.length < upper.length || lower[0] > currentDifference || lower[lower.length-1] > currentDifference || lower[lower.length-1] < upper[0]/lower.length) { return smallestDifference; } for (int i = lower.length-1; i >= 0 && smallestDifference > 0; i--) { newUpper = addElement(upper, lower[i]); newLower = removeElementAt(lower, i); smallestDifference = findSmallestDifference(newLower, newUpper, lowerSum - lower[i], upperSum + lower [i], smallestDifference); } return smallestDifference; } 

Data set

Here is an example kit that takes too long to solve.

{100000,60000,60000,60000,60000,60000,60000,60000,60000, 60000,60000,60000,60000,60000,60000,60000,60000,60000, 60,000,60000,60000,60000,60000,60000,60000 , 60000,60000, 60000,60000,60000}

If you need all the source code, I put it on Ideone .

Answer 1

Say N is the sum of all the coins. We need to find a subset of coins, where the sum of its coins is closest to N/2 . Let me calculate all possible amounts and choose the best. In the worst case, we can expect 2 ^ 30 possible amounts, but this may not happen, because the largest possible amount is 100K * 30, that is, 3M is much less than 2 ^ 30, which will be about 1G. Therefore, to store all possible amounts, an array of 3M int or 3M bits should be sufficient.

So, we have an array a and a[m] == 1 if and only if m is a possible sum.

We start with a zeroed array and have a[0]=1 , since the sum of 0 is possible (one does not have coins).

 for (every coin) for (int j=0; j<=3000000; j++) if (a[j] != 0) // j is a possible sum so far new_possible_sum = j + this_coin a[new_possible_sum] = 1 

When you finish in steps of 30 * 3M, you will find out all the possible amounts. Find the number m that is closest to N/2 . Your result is abs(Nm - m) . Hope I will fit in time and memory limits.

Edit : Correction required and 2 optimizations:

• Pass the array in descending order. Otherwise, a dollar coin would rewrite the entire array in one go.
• Limit the size of the array to N+1 (including 0) to solve smaller coin sets faster.
• Since we almost always get 2 identical results: m and Nm , reduce the size of the array to N/2 . Add a related check for new_possible_sum . Throw away the largest possible amounts.

Answer 2

EDIT , to be clear: I wrote this answer before the question stated an additional job restriction in less than five seconds. I also wrote this to show that sometimes brute force is possible even when it seems that it is not. Therefore, this answer should not be the "best" answer to this problem: it is definitely designed to solve brute force. As a side benefit, this small solution can help someone write another solution for validation at an acceptable time when their answer to the "large" arrays is correct.

The problem, of course, is that the number of possible traverse combinations is soon too large to search for brute force.

Given the problem, as originally stated (before the maximum runtime of 5 seconds was indicated), I completely dispute this statement;)

You specifically wrote that the maximum length is 30.

Please note that I am not talking about other solutions (for example, a dynamic software solution that may or may not work based on your limitations).

I say 2 ^{30 is} not big. This is a little more than one billion and that is it.

A modern processor can execute billions of cycles per second on a single core.

You do not need to reorganize to solve this problem: recursion should blow your stack. There is a simple way to determine the whole possible combination of left and right: just count from 0 to 2 exp 30 - 1 and check each bit (decide that, say, a little, so you put the value left and left, the value on the right).

So, if the problem statement, if I'm not mistaken, the following approach should work, without any optimization:

  public static void bruteForce( final int[] vals) { final int n = vals.length; final int pow = (int) Math.pow(2, n); int min = Integer.MAX_VALUE; int val = 0; for (int i = pow -1; i >= 0; i--) { int diff = 0; for ( int j = 0; j < n; j++ ) { diff += (i & (1<<j)) == 0 ? vals[j] : -vals[j]; } if ( Math.abs(diff) < min ) { min = Math.abs(diff); val = i; } } // Some eye-candy now... for ( int i = 0 ; i < 2 ; i ++ ) { System.out.print( i == 0 ? "Left:" : "Right:"); for (int j = 0; j < n; j++) { System.out.print(((val & (1 << j)) == (i == 0 ? 0 : (1<<j)) ? " " + vals[j] : "")); } System.out.println(); } } 

For example:

 bruteForce( new int[] {2,14,19,25,79,86,88,100}); Left: 2 14 25 79 86 Right: 19 88 100 bruteForce( new int[] {20,19,10,9,8,5,4,3}); Left: 20 19 Right: 10 9 8 5 4 3 

In an array of 30 elements on my cheap processor, it works after 125 seconds. This is for the "first project", a completely non-optimized solution running on one core (the problem, as indicated, is trivial for parallelization).

You can, of course, participate and reuse many, many and many intermediate results, therefore, solving an array of 30 elements in less than 125 seconds.