The answer by Yassin Hajaj shows one way of computing the optimal result for this particular case. More generally, what you are trying to solve is a special instance of the subset sum problem, and there are related questions - e.g. divide an array into two sets with minimal difference.
There basically is no efficient way of finding the optimal solution.
The brute-force way to compute the optimal solution is to compute all possible choices of half of the elements, compute their sum, and find the sum that has the least deviation from the desired sum.
However, in many cases, one is not interested in the optimal solution, but only in a "good" solution. This can be achieved with a greedy approach: First, sort the scores in decreasing order. Then, go through the list of team members, and assign each of them to the team that currently has the lower score.
Both approaches are implemented here, as an example:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.NoSuchElementException;
import java.util.Set;
import java.util.TreeMap;
public class MapSplit
{
public static void main(String[] args)
{
TreeMap<Integer, Double> teamScoreMap = new TreeMap<Integer, Double>();
teamScoreMap.put(1, 5.0);
teamScoreMap.put(2, 8.4);
teamScoreMap.put(3, 2.1);
teamScoreMap.put(4, 6.5);
teamScoreMap.put(5, 4.5);
teamScoreMap.put(6, 3.2);
teamScoreMap.put(7, 9.8);
teamScoreMap.put(8, 7.6);
solveOptimal(teamScoreMap);
solveGreedy(teamScoreMap);
}
private static void solveOptimal(Map<Integer, Double> teamScoreMap)
{
List<Entry<Integer, Double>> entries =
new ArrayList<Entry<Integer, Double>>(
teamScoreMap.entrySet());
double totalSum = computeSum(entries);
ChoiceIterable<Entry<Integer, Double>> ci =
new ChoiceIterable<Entry<Integer, Double>>(
teamScoreMap.size() / 2, entries);
List<Entry<Integer, Double>> bestTeam = null;
double minError = Double.POSITIVE_INFINITY;
for (List<Entry<Integer, Double>> team : ci)
{
double teamSum = computeSum(team);
double error = Math.abs(teamSum - totalSum * 0.5);
if (error < minError)
{
bestTeam = team;
minError = error;
}
}
Set<Entry<Integer, Double>> teamA =
new LinkedHashSet<Entry<Integer, Double>>(bestTeam);
Set<Entry<Integer, Double>> teamB =
new LinkedHashSet<Entry<Integer, Double>>(
teamScoreMap.entrySet());
teamB.removeAll(teamA);
System.out.println("Optimal result:");
printResult(teamA, teamB);
}
private static void solveGreedy(Map<Integer, Double> teamScoreMap)
{
List<Entry<Integer, Double>> entries =
new ArrayList<Entry<Integer, Double>>(
teamScoreMap.entrySet());
Collections.sort(entries, (e0, e1) ->
Double.compare(e1.getValue(), e0.getValue()));
Set<Entry<Integer, Double>> teamA =
new LinkedHashSet<Entry<Integer, Double>>();
double sumA = 0;
Set<Entry<Integer, Double>> teamB =
new LinkedHashSet<Entry<Integer, Double>>();
double sumB = 0;
for (Entry<Integer, Double> entry : entries)
{
if (sumA < sumB)
{
teamA.add(entry);
sumA += entry.getValue();
}
else
{
teamB.add(entry);
sumB += entry.getValue();
}
}
System.out.println("Greedy result:");
printResult(teamA, teamB);
}
private static void printResult(
Collection<Entry<Integer, Double>> teamA,
Collection<Entry<Integer, Double>> teamB)
{
System.out.println("Team A:");
for (Entry<Integer, Double> entry : teamA)
{
System.out.println(" " + entry);
}
System.out.println("Sum: " + computeSum(teamA));
System.out.println("Team B:");
for (Entry<Integer, Double> entry : teamB)
{
System.out.println(" " + entry);
}
System.out.println("Sum: " + computeSum(teamB));
}
private static double computeSum(
Collection<Entry<Integer, Double>> entries)
{
return entries.stream().map(
e -> e.getValue()).reduce(0.0, (a,b) -> a+b);
}
}
// From https://github.com/javagl/Combinatorics/blob/master/src/main/
// java/de/javagl/utils/math/combinatorics/CombinationIterable.java
class ChoiceIterable<T> implements Iterable<List<T>>
{
private final List<T> input;
private final int sampleSize;
private final long numElements;
public ChoiceIterable(int sampleSize, List<T> input)
{
this.sampleSize = sampleSize;
this.input = input;
BigInteger nf = factorial(input.size());
BigInteger kf = factorial(sampleSize);
BigInteger nmkf = factorial(input.size() - sampleSize);
BigInteger divisor = kf.multiply(nmkf);
BigInteger result = nf.divide(divisor);
numElements = result.longValue();
}
public static BigInteger factorial(int n)
{
BigInteger f = BigInteger.ONE;
for (int i = 2; i <= n; i++)
{
f = f.multiply(BigInteger.valueOf(i));
}
return f;
}
@Override
public Iterator<List<T>> iterator()
{
return new Iterator<List<T>>()
{
private int current = 0;
private final int chosen[] = new int[sampleSize];
// Initialization of first choice
{
for (int i = 0; i < sampleSize; i++)
{
chosen[i] = i;
}
}
@Override
public boolean hasNext()
{
return current < numElements;
}
@Override
public List<T> next()
{
if (!hasNext())
{
throw new NoSuchElementException("No more elements");
}
List<T> result = new ArrayList<T>(sampleSize);
for (int i = 0; i < sampleSize; i++)
{
result.add(input.get(chosen[i]));
}
current++;
if (current < numElements)
{
increase(sampleSize - 1, input.size() - 1);
}
return result;
}
private void increase(int n, int max)
{
if (chosen[n] < max)
{
chosen[n]++;
for (int i = n + 1; i < sampleSize; i++)
{
chosen[i] = chosen[i - 1] + 1;
}
}
else
{
increase(n - 1, max - 1);
}
}
@Override
public void remove()
{
throw new UnsupportedOperationException(
"May not remove elements from a choice");
}
};
}
}
(the class for computing the choices is taken from here)
The output is as follows:
Optimal result:
Team A:
1=5.0
4=6.5
5=4.5
8=7.6
Sum: 23.6
Team B:
2=8.4
3=2.1
6=3.2
7=9.8
Sum: 23.5
Greedy result:
Team A:
2=8.4
8=7.6
1=5.0
3=2.1
Sum: 23.1
Team B:
7=9.8
4=6.5
5=4.5
6=3.2
Sum: 24.0
showing that the greedy result is not the optimal one, but still rather good in this case.
