How to get maximum sum of numbers drawn from multiple arrays - permutation don't work (16!)

Question

Yesterday I asked about How to find the maximum possible sum of numbers in arrays drawn from a unique array index and I was advise to use permutation - it worked well, but I wasn't aware that my arrays are much bigger than I assumed. I have arrays as big as [16] - so I have 16! possibilites...what could I use instead of permutation to get maximum possible sum?

edit. here is my arrays:

public static ArrayList<Double[]> tempArrayCreator() {
    ArrayList<Double[]> tempArray = new ArrayList<>();

    Double[] l1 = { 9.0, 13.5, 9.0, 9.0, 9.0, 13.5, 9.0, 13.5, 13.5, 13.5,
            9.0, 13.5, 13.5, 9.0, 13.5, 9.0 };
    Double[] l2 = { 6.0, 6.0, 13.5, 6.0, 9.0, 6.0, 6.0, 6.0, 6.0, 9.0, 6.0,
            6.0, 9.0, 9.0, 6.0, 9.0 };
    Double[] l3 = { 22.5, 22.5, 14.0, 22.5, 14.0, 22.5, 22.5, 22.5, 22.5,
            21.0, 22.5, 22.5, 21.0, 14.0, 22.5, 14.0 };
    Double[] l4 = { 6.0, 6.0, 7.0, 6.0, 7.0, 6.0, 6.0, 6.0, 6.0, 7.0, 9.0,
            6.0, 7.0, 7.0, 6.0, 7.0 };
    Double[] l5 = { 4.5, 6.75, 6.0, 4.5, 6.0, 6.75, 4.5, 4.5, 6.75, 9.0,
            4.5, 6.75, 9.0, 6.0, 6.75, 6.0 };
    Double[] l6 = { 6.0, 9.0, 5.0, 6.0, 5.0, 9.0, 6.0, 6.0, 9.0, 7.5, 6.0,
            9.0, 7.5, 5.0, 9.0, 5.0 };
    Double[] l7 = { 13.5, 13.5, 4.0, 13.5, 4.0, 13.5, 13.5, 13.5, 13.5,
            6.0, 13.5, 13.5, 4.0, 4.0, 13.5, 4.0 };
    Double[] l8 = { 4.5, 4.5, 4.0, 4.5, 4.0, 4.5, 4.5, 4.5, 4.5, 4.0, 4.5,
            4.5, 6.0, 4.0, 4.5, 4.0 };
    Double[] l9 = { 10.5, 10.5, 10.0, 10.5, 10.0, 10.5, 10.5, 10.5, 10.5,
            10.0, 10.5, 10.5, 10.0, 10.0, 10.5, 10.0 };
    Double[] l10 = { 11.25, 11.25, 3.0, 11.25, 3.0, 11.25, 11.25, 11.25,
            11.25, 3.0, 11.25, 11.25, 3.0, 3.0, 11.25, 3.0 };
    Double[] l11 = { 7.5, 11.25, 10.0, 7.5, 10.0, 11.25, 7.5, 11.25, 11.25,
            15.0, 7.5, 11.25, 15.0, 10.0, 11.25, 10.0 };
    Double[] l12 = { 7.5, 7.5, 12.0, 7.5, 8.0, 7.5, 7.5, 7.5, 7.5, 8.0,
            7.5, 7.5, 8.0, 8.0, 7.5, 8.0 };
    Double[] l13 = { 13.5, 13.5, 6.0, 13.5, 6.0, 13.5, 13.5, 13.5, 13.5,
            9.0, 13.5, 13.5, 9.0, 6.0, 13.5, 6.0 };
    Double[] l14 = { 9.0, 9.0, 8.0, 9.0, 8.0, 9.0, 9.0, 9.0, 9.0, 12.0,
            9.0, 9.0, 12.0, 8.0, 9.0, 8.0 };
    Double[] l15 = { 7.5, 7.5, 12.0, 7.5, 8.0, 7.5, 7.5, 7.5, 7.5, 8.0,
            7.5, 7.5, 8.0, 8.0, 7.5, 8.0 };
    Double[] l16 = { 18.0, 18.0, 10.0, 18.0, 10.0, 18.0, 18.0, 18.0, 18.0,
            15.0, 18.0, 18.0, 15.0, 10.0, 18.0, 10.0 };

    tempArray.add(l1);
    tempArray.add(l2);
    tempArray.add(l3);
    tempArray.add(l4);
    tempArray.add(l5);
    tempArray.add(l6);
    tempArray.add(l7);
    tempArray.add(l8);
    tempArray.add(l9);
    tempArray.add(l10);
    tempArray.add(l11);
    tempArray.add(l12);
    tempArray.add(l13);
    tempArray.add(l14);
    tempArray.add(l15);
    tempArray.add(l16);

    return tempArray;
}

Answer 1

The solution with permutation is actually a backtracking solution: you compute all possible sums and take the maximum sum. Backtracking always gives a correct result (since it considers every possibility) but is very slow.

Another aproach would be by writing a Greedy Algorithm (easy and fast, but fails in a lot of cases).

By searching on google, i found that the best solution for your problem is given by applying the so-called Hungarian Algorithm: http://www.hungarianalgorithm.com/examplehungarianalgorithm.php In your case, you are trying to find the maximum sum (the example is for minimum sum)

Answer 2

If I have got it right you want to find the maximum sum of arrays created by another array that contains all elements and whose indices are going to be placed in your new arrays.

So how many arrays are going there to be? Anyway not really important. So why don't you take the max of each new array you have and just add it? And you might think "how do I know how the elements are going to be filled?".

Well, since you are only interested in the max sum you, you can take into consideration only the maximum N elements of your original array. You do know the elements in the original array, right? So imaging that those let's say 3 (N = 3) arrays have each one of them one of these N numbers then you just keep these and there you go!

I don't know if I am missing something but you don't need permutation if that's the case. If not then explain the situation a little better. Just sum the larger N numbers.

Edit:

Since you have 16 arrays of 16 elements you can imagine that each array is split into smaller ones (say 4-elemens each).

int[] arr1 = {x, x, x, x, x, x, 16, x, 20, x, x, ,19, x, x, x, 17};

where x is an arbitrary number that is smaller than 16 (the smaller of the 4 biggest numbers). It does not matter in which index it's going to be every one of these four numbers as long as they are not in the same index. So you can suppose that there (multiple) situation that they are not in the same index so the sum is just the sum of these 4 numbers. One possible permutation could be (but any other with the above condition would do):

int[] smallArr1 = {x, x, x, 16};
int[] smallArr2 = {x, x, 17, x};
int[] smallArr3 = {x, 19, x, x};
int[] smallArr4 = {20, x, x, x};

So sum is just

int sum = 16 + 17 +19 + 20;

in any case.

Answer 3

I hope I do not misunderstand you but my solution would be to draw the biggest out of every ArrayIndex and then sum them up, because the biggest result consists of all biggest elements

public double maxPossibleSum(ArrayList<Double[]> lists) {

    double result = 0.0;

    for (int i = 0; i < lists.get(0).length; i++) {

    double biggest = lists.get(0)[i];

        for (int j = 1; j < lists.size(); j++) {

            if(lists.get(j)[i] > biggest){ //Find 

                biggest = lists.get(j)[i];
            }

            result += biggest;
        }
    }

    return result;
}