
Now let's solve VectorMatching. In this problem we are given n points and we are asked to find a vector matching that has the minimal length. The number of points is small (n=20) which allows us to iterate over all possible vector matchings. A vector matching consists of two sets of points A and B, such that the head of the ith vector is the ith point in A and its tail is the ith point in B. A and B should have the same number of elements, namely n/2. Each point can be either in set A or in set B, so we have 2^n possible states. However, we only need to consider those states where the size of A is n/2. This reduces the problem to Choose(20,10) = 185756 states.
Suppose the point (x1,y1) is in A and the point (x2,y2) is in B. The vector represented by these two points is (x2x1,y2y1). Hence if a point is in A then it contributes negatively to the vector sum; otherwise it is in B and it contributes positively. So now we can determine the vector sum (which is a vector) as we iterate through the points in A and B; its xcomponent will be sumX and its ycomponent will be sumY:
public class VectorMatching
{
public double minimumLength(int[] x, int[] y)
{
double result = Double.MAX_VALUE;
int n = x.length;
for (int i = 0; i < (1 << n); i++)
{
//size of A and B must be n/2
if (2*Integer.bitCount(i) != n) continue;
long sumX = 0;
long sumY = 0;
for (int k = 0; k < n; k++)
{
//point (x[k],y[k]) is in B
if ((i&(1<<k)) > 0)
{
sumX += x[k];
sumY += y[k];
}
//point (x[k],y[k]) is in A
else
{
sumX = x[k];
sumY = y[k];
}
}
double length=Math.sqrt(sumX*sumX + sumY*sumY); //vector length
result = Math.min(result,length); //record the minimum length
}
return result;
}
}
