当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(

发表于: 2012-12-27   作者:bylijinnan   来源:转载   浏览:
摘要: 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|)最大
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;
    }
    
}

bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
主要是凸包算法、卡壳算法 http://blog.csdn.net/kaytowin/archive/2010/01/06/5140111.aspx http:/
原文链接:http://blog.csdn.net/zhangxaochen/article/details/8027003 突然就想钻钻牛角尖,搞搞
题目 数轴上从左到右有n各点a[0], a[1], ……,a[n -1],给定一根长度为L的绳子,求绳子最多能覆盖其
2007/11/23 15:44 安规电容是指用于这样的场合,即电容器失效后,不会导致电击,不危及人身安全. 它
编程实现任意一个数的阶乘 #include<stdio.h> main() { int n,i; long f=1; puts("please inp
题目:求1 + 2 + 3 + ... + n 的和 要求:不能使用乘除法、for、while、if、else、switch、case等关
我们知道C++中是有pow函数的,我们这次自己来写个,因为有这样的算法题目。 所需数学知识: 大致考
我的算法思想和实现方式都在代码和注释当中呢,这样的方式确实使算法复杂度降低一个等级,很好啊。
我的算法思想和实现方式都在代码和注释当中呢,这样的方式确实使算法复杂度降低一个等级,很好啊。
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号