算法学习——贪心

贪心算法的经典算法，如埃及分数、TSP问题、图着色问题、背包问题等。

贪心

经典算法

埃及分数

public static void EgyptFrac(int A, int B) {
    int E, R;
    System.out.println(A + "/" + B + "=");
    do {
        E = B / A + 1;// 求A/B包含的最大埃及分数
        System.out.println("1/" + E + "+");
        A = A * E - B;// 本行及下一行求A/B - 1/E
        B = B * E;
        R = CommFactor.getCommFactor(B, A);// 求A，B最大公约数
        if (R > 1) {// 化简A/B
            A = A / R;
            B = B / R;
        }
    } while (A > 1);// 当A/B不是埃及分数时继续循环
    System.out.println("1/" + B);
}

欧几里得法求公约数（即辗转相除法）

public static int getCommFactor(int m, int n) {
    int r = m % n;
    while (r != 0) {
        m = n;
        n = r;
        r = m % n;
    }
    return n;
}

TSP问题

最近邻点策略（类似Prim算法）

public static int TSP1(int[][] arc, int w) {// arc为邻接矩阵，w为出发顶点
        int edgeCount = 0, TSPLength = 0;
        int min, u, v = 0;
        int n = arc.length;
        int[] flag = new int[n];// 标记顶点是否在哈密顿回路中
        u = w;
        flag[w] = 1;
        while (edgeCount < n - 1) {// 哈密顿回路中只有n-1条边
            min = 1000;
            for (int j = 1; j < n; j++) {// 求整个邻接矩阵中的最小值
                if ((flag[j] == 0) && (arc[u][j] != 0) && (arc[u][j] < min)) {
                    v = j;
                    min = arc[u][j];
                }
            }
            TSPLength += arc[u][v];
            flag[v] = 1;// 将顶点加入哈密顿回路
            edgeCount++;
            System.out.println(u + "--->" + v);
            u = v;// 更新下次出发的顶点
        }
        System.out.println(v + "--->" + w);
        return TSPLength + arc[u][w];
    }

最短链接策略（类似Kruskal算法）（待解决）

图着色问题

private static int[] color;

public static int ColorGraph(int[][] arc) {
    int k = 0;
    int n = arc.length;
    color = new int[n];
    boolean flag = true;// flag为true表示图中还有顶点未着色
    while (flag) {
        k++;
        flag = false;
        for (int i = 0; i < n; i++) {
            if (color[i] == 0) {
                color[i] = k;// 顶点i着色k
                if (!Ok(arc, i)) {// 发生冲突，取消着色
                    color[i] = 0;
                    flag = true;
                }
            }
        }
    }
    System.out.println(Arrays.toString(color));

    return k;
}

public static boolean Ok(int[][] arc, int i) {// 判断顶点i的着色是否发生冲突
    for (int j = 0; j < arc.length; j++) {// 考察其他所有顶点
        if (arc[i][j] == 1 && color[i] == color[j])// arc矩阵为无向图的邻接矩阵，1表示连通，0表示不连通
            return false;
    }
    return true;
}

最小生成树问题

Prim算法

public static void Prim(int[][] arc, int w) {// 从顶点w出发，初始集合U={}
    int i, j, k = 0;
    int min;
    int n = arc.length;
    ShortEdge[] shortEdges = new ShortEdge[n];// 存储候选的边集合
    for (i = 0; i < n; i++) {
        shortEdges[i] = new ShortEdge();
    }
    for (i = 0; i < n; i++) {// 初始化辅助数组
        shortEdges[i].setLowcost(arc[w][i]);
        shortEdges[i].setAdjvex(w);
    }
    shortEdges[w].setLowcost(0);// 将顶点w加入集合U
    for (i = 0; i < n - 1; i++) {
        min = 1000;// 设权值不超过1000
        for (j = 0; j < n; j++) {// 寻找最短边的邻接点k
            if ((shortEdges[j].getLowcost() != 0) && (shortEdges[j].getLowcost() < min)) {
                min = shortEdges[j].getLowcost();
                k = j;
            }
        }
        System.out.println(shortEdges[k].getAdjvex() + "---" + k);// 输出最小生成树的边
        shortEdges[k].setLowcost(0);// 将顶点k加入集合U中
        for (j = 0; j < n; j++) {// 调整数组shortEdge[n]
            if (arc[k][j] < shortEdges[j].getLowcost()) {
                shortEdges[j].setLowcost(arc[k][j]);
                shortEdges[j].setAdjvex(k);
            }
        }
    }
}

Kruskal算法（待解决）

背包问题

注意：不同于0/1背包问题，背包问题中的物品无需整个放入，可以只放一个物品的一部分

为了方便，默认物品是按照单位价值降序排列的

public static double KnapSack(int[] w, int[] v, int C) {
    double[] x = new double[w.length];// 记录物品装入的部分
    int i;
    double maxValue = 0;
    for (i = 0; w[i] < C; i++) {
        x[i] = 1;
        maxValue += v[i];
        C = C - w[i];
    }
    x[i] = (double) C / w[i];
    maxValue += x[i] * v[i];
    return maxValue;
}

活动安排问题

将活动按照结束时间非降序排列

public static int ActiveManage(int[] s, int[] f) {
    int i, j, count;
    int n = s.length;
    int[] B = new int[n];
    B[0] = 1;// 安排活动1
    j = 0;
    count = 1;
    for (i = 1; i < n; i++) {// 依次考察每个活动
        if (s[i] >= f[j]) {// 活动i与集合B中最后结束的活动j相容
            B[i] = 1;// 安排活动i
            j = i;// j是目前可以安排的最后一个活动
            count++;
        } else {
            B[i] = 0;
        }
    }

    System.out.println(Arrays.toString(B));
    return count;// 返回已经安排的活动数
}

多机调度问题

将作业处理时间按非升序排列

public static void MultiMachine(int[] t, int[] d) {// t存储n个作业的处理时间，d存储m台机器的已占用时间
    int n = t.length, m = d.length;// m台机器，n个任务
    int[][] S = new int[m][n];// S[i]存储机器i处理作业的队列，rear[i]为队尾下标
    int[] rear = new int[m];
    int i, j, k;

    for (i = 0; i < m; i++) {// 初始化S
        for (j = 0; j < n; j++) {
            S[i][j] = -1;
        }
    }

    for (i = 0; i < m; i++) {// 安排前m个作业
        S[i][0] = i;
        rear[i] = 0;
        d[i] = t[i];
    }
    for (i = m; i < n; i++) {// 依次安排余下的作业
        for (j = 0, k = 1; k < m; k++) {// 查找最先空闲的机器
            if (d[k] < d[j])
                j = k;
        }
        rear[j]++;
        S[j][rear[j]] = i;// 将作业i插入队列S[j]
        d[j] = d[j] + t[i];
    }
    for (i = 0; i < m; i++) {
        System.out.println("机器" + i + ":");
        for (j = 0; S[i][j] >= 0; j++) {
            System.out.println("---作业" + S[i][j]);
        }
    }
}