Divide the array in equal size so that the value of the given function is minimal

Question

I ran into the following problem.

You have a list of natural numbers of size N , and you must distribute the values ​​in two lists A and B size N/2 , so that the square of the sum of the elements of A is the closest possible to multiply the elements of B

Example: Consider a list of 7 11 1 9 10 3 5 13 9 12.
Optimized Distribution:
List A: 5 9 9 12 13
List B: 1 3 7 10 11
which leads to the difference abs ((5 + 9 + 9 + 12 + 13) ^ 2 - (1 * 3 * 7 * 10 * 11)) = 6 Therefore, your program should output 6, which is the minimum difference that can be achieved .

What I tried:

I tried the Greedy approach to solve this problem. I took two variables sum and mul . Now I began to take elements from a given set one by one and tried to add it to both the variables and the calculated current square of the sum and multiplication. Now complete the element in one of two sets so that the combination gives the lowest possible value.

But this approach does not work in this example itselt. I cannot figure out which approach can be used here.

I am not asking for the exact code for the solution. Any possible approach and the reason it works will be fine.

EDIT:

Source: CodinGame, community puzzle

Answer 1

Try the following:

 import java.util.Arrays; public class Test { public static void main(String [] args){ int [] arr = {7, 11, 1, 9, 10, 3, 5, 13, 9, 12}; int [][] res = combinations(5, arr); int N = Arrays.stream(arr).reduce(1, (a, b) -> a * b); int min = Integer.MAX_VALUE; int [] opt = new int [5]; for (int [] i : res){ int k = (int) Math.abs( Math.pow(Arrays.stream(i).sum(), 2) - N/(Arrays.stream(i).reduce(1, (a, b) -> a * b))); if(k < min){ min = k; opt = i; } } Arrays.sort(opt); System.out.println("minimum difference is "+ min + " with the subset containing this elements " + Arrays.toString(opt)); } // returns all k-sized subsets of a n-sized set public static int[][] combinations(int k, int[] set) { int c = (int) binomial(set.length, k); int[][] res = new int[c][Math.max(0, k)]; int[] ind = k < 0 ? null : new int[k]; for (int i = 0; i < k; ++i) { ind[i] = i; } for (int i = 0; i < c; ++i) { for (int j = 0; j < k; ++j) { res[i][j] = set[ind[j]]; } int x = ind.length - 1; boolean loop; do { loop = false; ind[x] = ind[x] + 1; if (ind[x] > set.length - (k - x)) { --x; loop = x >= 0; } else { for (int x1 = x + 1; x1 < ind.length; ++x1) { ind[x1] = ind[x1 - 1] + 1; } } } while (loop); } return res; } // returns n choose k; // there are n choose k combinations without repetition and without observance of the sequence // private static long binomial(int n, int k) { if (k < 0 || k > n) return 0; if (k > n - k) { k = n - k; } long c = 1; for (int i = 1; i < k+1; ++i) { c = c * (n - (k - i)); c = c / i; } return c; } } 

Code taken from https://stackoverflow.com/a/312947/ ... also see this wikipedia article on combinations.

Answer 2

I am not sure if there is any exact solution in polynomial time. But you could try using an annealing based simulation method.

My approach:

• Initialize listA and listB in random state
• With probability p, run the greedy step; otherwise, execute a random step
• Keep track of the status and associated error (using HashMap)

The greedy step: find one item that you can move between the list that optimizes the error.

Random step: select a random element from any of these two sets and calculate the error. If the error is better, save it. Otherwise, save it with probability q.

At either of these two steps, make sure that the new state has not yet been studied (or at least scares him off).

Set p to a small value (<0.1) and q may depend on the difference in errors.