Finding the maximum combined total in Java [closed]

Question

Suppose you had a set of numbers like below:

[A,B,C]

[6, 4.5, 6]
[7, 6, 5]
[9, 4.5, 6]

Only one number from each set AND of a category (A, B, or C) may be used to find the greatest sum. In this case, A=9, B=6, and C=6 will produce the greatest sum of 21. The greatest sum cannot be 22 (9+7+6) because 9 and 7 conflict by both being category A.

How can I do this in Java?

I am having trouble finding the largest sum because picking the largest value in each category does not guarantee the largest sum. Some categories may be forced into smaller values decreasing the sum. Remember that only one number from each set AND of a category may be chosen.

Answer 1

It sounds a bit like the Eight Queens Puzzle, where you have to place 8 queens on a chessboard without any of them in the path of another. (If you don't know chess, don't fret over the analogy).

Suppose your example array:

[6, 4.5, 6]
[7,   6, 5]
[9, 4.5, 6] 

Find the largest value overall (in this case 9), and block out its column and row.

Your new array looks like this (with x's as choices no longer valid).

[x, 4.5, 6]
[x,   6, 5]
[x,   x, x]

Repeat that process over and over until you have chosen one value from each column and each row.

Now, as a warning, having multiple locations for the current max (as in the second step of the example, with the two 6s) leads to some more conditions. I will leave some of the fun with you, but will gladly give more help if it is needed.

Warning

This answer is not valid, as pointed out by Neil C. in the comments. Specific counterexample:

[10, 9, 1]
[ 9, 1, 1]
[ 1, 1, 1]

I don't have the fix at hand yet, but I want to leave this answer available for help in coming up with the correct solution.