bitmap求哈密顿距离-给定N（1<=N<=100000）个五维的点A(x1,x2,x3,x4,x5)，求两个点X(x1,x2,x3,x4,x5)和Y(
import java.util.Random;/** * 题目： * 给定N（1<=N<=100000）个五维的点A(x1,x2,x3,x4,x5)，求两个点X(x1,x2,x3,x4,x5)和Y(y1,y2,y3,y4,y5)， * 使得他们的哈密顿距离（d=|x1-y1| + |x2-y2| + |x3-y3| + |x4-y4| + |x5-y5|）最大。|x|=abs(x)。 * * 第一种方法当然是暴力遍历一次，求得最大值 * 第二种方法借助bitmap * 在网上找了两个相关的资料： * http://www.cppblog.com/sonicmisora/archive/2009/09/14/96143.aspx * http://wenku.baidu.com/view/1e51750abb68a98271fefaa8.html * * 我觉得这两个资料都不好理解 * 我的理解如下： * 1. * 这道题目里面，使用bitmap的关键是这个： * 先看二维的点，我们约定形如Xij下标的数字(ij)是二进制，0表示正数，1表示负数，令 * X00= x1 + x2 * X01= x1 - x2 * X10= - x1 + x2 * X11= - x1 - x2 * 用一个一维数组a保存这四个值，即a[0]=X00,a[1]=X01,a[2]=X10,a[3]=X11 * 有N个点，那么就有二维数组：A[N][S],(S=00,01,10,11) * * 2.(当然，更严谨的数学证明请参考上面提到的第二个链接) * |x1-y1| = MAX(x1-y1, y1-x1); * => |x1-y1| + |x2-y2| = MAX{ (x1-y1)+(x2-y2) (x1-y1)-(x2-y2) -(x1-y1)+(x2-y2) -(x1-y1)-(x2-y2) }; 也就是= MAX{ (x1+x2)-(y1+y2) (x1-x2)-(y1-y2) (-x1+x2)-(-y1+y2) (-x1-x2)-(-y1-y2) }; 正好是MAX{(X00-Y00), (X01-Y01), (X10-Y10), (X11-Y11)}; 如果有A-Z共26个点，那么 result = MAX{ (A00-B00), (A01-B01), (A10-B10), (A11-B11), (A00-C00), (A01-C01), (A10-C10), (A11-C11), ...... (X00-Y00), (X01-Y01), (X10-Y10), (X11-Y11), (Y00-Z00), (Y01-Z01), (Y10-Z10), (Y11-Z11), }; 对上面的每一列应用MAX运算： 对ij=00，时，第一列有MAX(第一列)=MAX(A00,B00...Z00) - Min(A00,B00...Z00) 那么 result = MAX{MAX(第一列),MAX(第二列)...}; 也就是上面提到的第一个链接里面的说法，引用一下： A[1][0]-A[2][0] A[1][1]-A[2][1] A[1][2]-A[2][2] A[1][3]-A[2][3] 然后问题就变得简单了，扫一遍，对于每个I，求出A[*][I]的最大值MAX(I)最小值MIN(I)， 再用MAX(I)-MIN(I)就可以得到对于I来说的最大值了。最后取个总的最大值 * @author bylijinnan */public class HamiltonDistance { private final int N = 10 * 1000; private final int D = 5; private final int S = 1 << D; public static void main(String[] args) { HamiltonDistance h = new HamiltonDistance(); h.test(); } public void test() { int[][] data = sourceData(); System.out.println(maxHamiltonDistance(data)); System.out.println(maxHamiltonDistanceBitMap(data)); } /** * 通过枚举暴力求解 * @param data * @return */ public long maxHamiltonDistance(int[][] data) { if (data == null || data.length != N || data[0].length != D) { System.out.println("invalid input"); return 0L; } long result = 0L; for(int i = 0; i < N; i++) { int[] pointA = data[i]; for(int j = i + 1; j < N; j++) { int[] pointB = data[j]; long distance = distanceOfTwoPoints(pointA, pointB); if (result < distance) { result = distance; } } } return result; } //求得：|X1-Y1| + |X2-Y2| + |X3-Y3| + |X4-Y4| + |X5-Y5| + ...|Xn-Yn| private long distanceOfTwoPoints(int[] pointA, int[] pointB) { long result = 0L; for(int i = 0; i < D; i++) { result += Math.abs((long)pointA[i] - (long)pointB[i]); } return result; } /** * 通过bitmap求解 * @param data * @return */ public long maxHamiltonDistanceBitMap(int[][] data) { //略去输入合法性检查 long result = Long.MIN_VALUE; //求得X00000~X11111，下标是二进制 long[][] A = new long[N][S]; for (int i = 0; i < N; i++) { for (int j = 0; j < S; j++) { A[i][j] = getSumByBits(data[i], j); } } //System.out.println(Arrays.deepToString(A)); long MAXi = Long.MIN_VALUE; long MINi = Long.MAX_VALUE; for (int i = 0; i < S; i++) { for (int j = 0; j < N; j++) { if (MAXi < A[j][i]) { MAXi = A[j][i]; } if (MINi > A[j][i]) { MINi = A[j][i]; } } result = max(result, (MAXi - MINi)); MAXi = Long.MIN_VALUE; MINi = Long.MAX_VALUE; } return result; } //0表示正数，1表示负数 private long getSumByBits(int[] a, int s) { long result = 0L; for (int i = 0; i < D; i++) { if (exist(s, i)) { result -= a[i]; } else { result += a[i]; } } return result; } //value的二进制表示，在第offset位是否为1 private boolean exist(int value, int offset) { //return (value & (1 << offset)) == 1; return (value & (1 << offset)) != 0; } //生成指定维度的N个点 private int[][] sourceData() { int[][] data = new int[N][D]; Random random = new Random(); for (int i = 0; i < N; i++) { for (int j = 0; j < D; j++) { int value = random.nextInt(); data[i][j] = value; } } return data; } private long max(long x, long...yy) { long result = x; for(long y : yy) { if (result < y) { result = y; } } return result; } }