将数组分割成差值最小的子集

本文使用位掩码实现一个功能 ==》将数组分割成差值最小的子集
代码如下：

import java.util.Arrays;

public class MinimalDifference {

	/**
	 * 将数组分割成差值最小的子集
	 */
	public void printTwoMinDiffGroups(int[] values) {

		int length = values.length;
		// 长度为length的二进制表示个数有1<<length个
		int allMasks = 1 << length;
		int min = Integer.MAX_VALUE;
		int value = 0;
		for (int i = allMasks - 1; i >= 0; i--) {
			int diff = 0;
			for (int j = 0; j < length; j++) {
				diff += (i & (1 << j)) == 0 ? values[j] : -values[j];

			}
			if (Math.abs(diff) < min) {
				min = Math.abs(diff);
				value = i;
			}
		}

		/*
		 * 将上述计算得到的value值，与二进制表示相比较
		 * 
		 * 1. value & (1 << j)) == 0 2. ((value & (1 << j)) == (1 << j))
		 */

		System.out.printf("原数组  %s 分割成两个和最接近的数组如下：\n", Arrays.toString(values));
		System.out.print("数组一的内容: ");
		for (int j = 0; j < length; j++) {
			System.out.print(((value & (1 << j)) == 0) ? values[j] + " " : "");
		}

		System.out.print("\n数组二的内容: ");
		for (int j = 0; j < length; j++) {
			System.out.print(((value & (1 << j)) == (1 << j)) ? values[j] + " "
					: "");
		}

	}

}

一个测试例子, 分割数组[1, 2, 3, 6, 4, 7, 9]。

public class Test {

	public static void main(String[] args) {
			new MinimalDifference().printTwoMinDiffGroups(new int[] { 1, 2, 3, 6,
					4, 7, 9 });
	}
}

运行结果：

原数组  [1, 2, 3, 6, 4, 7, 9] 分割成两个和最接近的数组如下：
数组一的内容: 1 2 3 6 4
数组二的内容: 7 9