第四章-贪心

活动安排

算法分析

想法很简单：就是先将活动结束时间按从小到大排个序，然后选择最早的的一个活动，这个活动的开始时间晚于当前集合中最后一个活动的结束时间，加入集合后将集合中结束时间重新修改为刚才加入活动的结束时间

代码

public class GreedySelector<Type> {

    public void greedySelector(int n, Type[] s, Type[] f, boolean[] A) {
        A[0] = true;
        int j = 0;
        for (int i = 1; i < n; i++) {
            if (((Comparable<Type>) s[i]).compareTo(f[j]) >= 0) {
                A[i] = true;
                j = i;
            } else {
                A[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        GreedySelector<Integer> greedySelector = new GreedySelector<>();
        int n = 5;
        Integer[] s = {0, 1, 3, 0, 5};
        Integer[] f = {2, 4, 5, 6, 8};
        boolean[] A = new boolean[n];
        greedySelector.greedySelector(n, s, f, A);
        System.out.print("A[]: ");
        for (boolean b : A) {
            System.out.print(b ? "true " : "false ");
        }
    }
}

背包问题

算法分析

这里的物品是可以“拆分”的，不像前面0-1背包物品一个一个都是完整的

贪心：将尽可能多高“性价比"货物放入背包，这里的”性价比“计算是\(\frac{货物价格}{货物重量}\)

代码

import java.util.Arrays;

public class Knapsack {

    public void knapsack(int n, float M, float[] v, float[] w, float[] x) {
        sort(n, v, w);
        for (int i = 0; i < n; i++) {
            x[i] = 0;
        }
        float c = M;
        int i;
        for (i = 0; i < n; i++) {
            if (w[i] > c) {
                break;
            }
            x[i] = 1;
            c -= w[i];
        }
        if (i < n) {
            x[i] = c / w[i]; // 最后装入部分物品
        }
    }

    private void sort(int n, float[] v, float[] w) {
        // 假设已经实现排序算法
        // 这里使用Arrays.sort()进行排序
        float[][] items = new float[n][2];
        for (int i = 0; i < n; i++) {
            items[i][0] = v[i];
            items[i][1] = w[i];
        }
        Arrays.sort(items, (a, b) -> Float.compare(b[0] / b[1], a[0] / a[1]));

        for (int i = 0; i < n; i++) {
            v[i] = items[i][0];
            w[i] = items[i][1];
        }
    }

    public static void main(String[] args) {
        Knapsack knapsack = new Knapsack();
        int n = 5;
        float M = 10;
        float[] v = {10, 20, 30, 40, 50};
        float[] w = {2, 3, 5, 7, 1};
        float[] x = new float[n];
        knapsack.knapsack(n, M, v, w, x);
        System.out.print("x[]: ");
        for (float value : x) {
            System.out.print(value + " ");
        }
    }
}

动态规划和贪心的相似与区别

动态规划是先解决子问题然后选择一个最好的解决方案，像0-1背包中dp数组

贪心是先选择一个解决方案然后再解决子问题，像活动安排时先找第一个活动一样

视频讲解：课堂老师讲解原声大碟

最优装载

算法分析

目标尽可能多，所以就先装重量小的

代码

import java.util.Arrays;

public class Loading<Type> {

    public void loading(int[] x, Type[] w, Type c, int n) {
        Integer[] t = new Integer[n + 1];
        for (int i = 0; i <= n; i++) {
            t[i] = i;
        }
        sort(w, t, n);  // 将所有集装箱按重量排序
        Arrays.fill(x, 0);
        for (int i = 1; i <= n && w[t[i]] <= c; i++) {
            x[t[i]] = 1;
            c = c - w[t[i]];  
        }
    }

    private void sort(Type[] w, Integer[] t, int n) {
        // 假设已经实现排序算法
        // 这里使用Arrays.sort()进行排序
        Arrays.sort(t, 1, n + 1, (a, b) -> compare(w[b], w[a])); // 根据重量w进行排序

        // 输出排序结果
        System.out.println("Sorted indexes:");
        for (int i = 1; i <= n; i++) {
            System.out.print(t[i] + " ");
        }
        System.out.println();
    }

    // 比较方法，假设 Type 类型实现了 Comparable 接口
    private int compare(Type a, Type b) {
        if (a instanceof Comparable && b instanceof Comparable) {
            return ((Comparable<Type>) a).compareTo(b);
        } else {
            throw new IllegalArgumentException("Type must implement Comparable interface");
        }
    }

    public static void main(String[] args) {
        Loading<Integer> loading = new Loading<>();
        int n = 5;
        Integer[] w = {3, 4, 5, 6, 7}; // 集装箱重量
        int[] x = new int[n + 1]; // 装载情况
        int c = 10; // 船的载重量
        loading.loading(x, w, c, n);
        System.out.print("x[]: ");
        for (int value : x) {
            System.out.print(value + " ");
        }
    }
}

哈夫曼编码

算法思路

维护一个小顶堆，每次从这个小顶堆中弹出最小和次小，相加后再放回，不断重复直到堆中只有1个节点

计算

平均码长

单源最短路

算法思路

每次根据dis数组将距离当前节点集合最近的节点加入集合，然后重新修改dis，并且也修改记录前驱节点的数组prev

最小生成树

Prim算法

算法原理

和迪杰斯特拉很像，也是维护dis数组，记录距离当前集合距离，每次将距离当前集合最近的节点放入集合

Kruskal算法

算法原理

每次将权值最小的边加入集合

多机调度

算法思想

优先安排耗时最长的任务