贪心算法的一些题目

活动安排问题

定义(活动) 设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,而在同一时间只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si <fi 。如果选择了活动i,则它在半开时间区间[si, fi)内占用资源。

解题思路

为了选择最多的相容活动,每次选fi 最小的活动,使我们能够选更多的活动。存储各个活动的开始时间和结束时间: 数组按照结束时间非递减排序。

  • 第一个活动一定是占用时间最短的
  • 从第二个活动开始遍历,但凡遍历到一个活动符合要求,那么这个活动一定是上一个活动结束后,符合开始时间且结束时间最早的活动。

编程实现

public int ActivitySelector(int[][] Activity){
    //将数组进行按结束时间从小到大排序
    Arrays.sort(Activity, new Comparator<int[]>() {
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[1]-o2[1];
        }
    });
    int[] s=new int[Activity.length],f=new int[Activity.length];
    boolean[] result=new boolean[Activity.length];
    for(int i=0;i<Activity.length;i++){
        s[i]=Activity[i][0];
        f[i]=Activity[i][1];
    }
    GreedySelector(s,f,result);
    int count=0;
    for(Boolean each:result){
        if(each)
            count++;
    }
    return count;
}

public void GreedySelector(int s[], int f[], boolean Activity[])
{
    Activity[0]=true;
    int j=1;
    for (int i=1;i<s.length;i++) {
        if (s[i]>=f[j]) { Activity[i]=true; j=i; }
        else Activity[i]=false;
    }
}

哈夫曼编码

import java.util.*;

public class Main {

    private static PriorityQueue<HufNode> hufList = new PriorityQueue<>(new Comparator<HufNode>() {
        @Override
        public int compare(HufNode o1, HufNode o2) {
            if (o1.value<o2.value) {
                return -1;
            }else if (o1.value == o2.value) {
                return 0;
            }else {
                return 1;
            }
        }
    });//容器存放节点值
    class HufNode{
        int value;
        String name;
        HufNode Lchild = null;
        HufNode Rchild = null;

        public HufNode(int v,String s){
            value = v;
            name = s;
        }
        public HufNode(HufNode l,HufNode r){
            Lchild =l;
            Rchild =r;
            value = Lchild.value + Rchild.value;
        }
    }
    //哈夫曼编码
    public void HufmanCode(int[] times,String[] names){
        for(int i=0;i<times.length;i++){
            hufList.offer(new HufNode(times[i],names[i]));
        }
        if (hufList.size()==1) {
            return;
        }
        while(hufList.size()>1){
            HufNode node = new Main().new HufNode(hufList.poll(),hufList.poll());
            hufList.offer(node);
        }//此时hufList中只有一个元素,这就是编码后的哈夫曼树的根节点
    }
    //解码,后序遍历
    public void decode(HufNode n,String code){
        if ((n.Lchild==null)&&(n.Rchild==null)) {
            System.out.print("元素值为 "+n.name+"   编码为:"+code);
            System.out.println();
            return;
        }
        decode(n.Lchild, code+"0");
        decode(n.Rchild, code+"1");
        return;
    }

    public static void main(String args[]) {
        Main main = new Main();
        int[] a=new int[]{10,15,12,3,4,13,1};
        String[] b=new String[]{"a","e","i","s","t","space","newline"};
        main.HufmanCode(a,b);
        main.decode(hufList.peek(),"");
    }
}

单源有向最短路径问题(Dijkstra算法)

从一个点出发到各个点的最短路径,两个算法,个人认为第一个写的好一点

/**
 * 单源最短路径
 *
 * @param v    顶点
 * @param map  图用二维数组表示
 * @param dist 从顶点到每个点的距离用数组表示
 * @param prev 前驱结点数组
 */
public static void dijkstra(int v, float[][] map, float[] dist, int[] prev) {
    int n = dist.length - 1;
    if (v < 1 || v > n) return;//合法性检测
    boolean[] put = new boolean[n + 1];//顶点放入或不放入的标志
    //初始化
    for (int i = 1; i <= n; i++) {
        dist[i] = map[v][i];
        put[i] = false;
        if (dist[i] == -1)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;//顶点放入
    put[v] = true;
    for (int i = 1; i < n; i++) {//共扫描n-1次
        float temp = Float.MAX_VALUE;
        int u = v;//u存放下一个被放入的点
        for (int j = 1; j <= n; j++) {//循环找到下一个距离最短的点
            if (!put[j] && dist[j] < temp && dist[j] != -1) {
                u = j;
                temp = dist[j];
            }
        }
        put[u] = true;
        for (int j1 = 1; j1 <= n; j1++) {//循环更改每个点的最短距离
            if (!put[j1] && map[u][j1] != -1) {
                float newdist = dist[u] + map[u][j1];
                if (newdist < dist[j1] || dist[j1] == -1) {
                    dist[j1] = newdist;
                    prev[j1] = u;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        System.out.println(i + "节点的最短距离是:" + dist[i] + ";前驱点是:" + prev[i]);
    }
}

public static void main(String[] args) {
    //节点个数
    int N = 5;
    float[][] distance = new float[N + 1][N + 1];
    float[] dist = new float[N + 1];
    int[] prev = new int[N + 1];
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) {
                distance[i][j] = 0;
            } else {
                distance[i][j] = -1;
            }
        }
    }
    distance[1][2] = 10;
    distance[1][4] = 30;
    distance[1][5] = 100;
    distance[2][3] = 50;
    distance[3][5] = 10;
    distance[4][5] = 60;
    distance[4][3] = 20;
    dijkstra(1, distance, dist, prev);
}

 

public static void Dijkstra(int N,int[][] distance) {
    
    int[] visit=new int[N+1],bestmin=new int[N+1];
    int max=Integer.MAX_VALUE;
    String[] path=new String[N+1];
    
    visit[1] = 1;
    bestmin[1] = 0;
    
    Arrays.fill(bestmin,max);
    
    for(int i=1;i<=N;i++){
        path[i] = new String("1-->" + i);
    }
    
    //大循环(搞定这里就算搞定该算法了,后面的输出什么的可以不看)
    for(int l = 2; l <= N; l++) {
        int Dtemp = max;
        int k = -1;
        //步骤①
        for(int i = 2; i <= N; i++) {
            if(visit[i] == 0 && distance[1][i] < Dtemp) {
                Dtemp = distance[1][i];
                k = i;
            }
        }
        visit[k] = 1;
        bestmin[k] = Dtemp;

        //步骤②
        for(int i = 2; i <= N; i++) {
            if(visit[i] == 0 && (distance[1][k] + distance[k][i]) < distance[1][i]) {
                distance[1][i] = distance[1][k] + distance[k][i];
                path[i] = path[k] + "-->" + i;
            }
        }
    }

    //输出路径
    for(int i=1;i<=N;i++) {
        System.out.println("从"+1+"出发到"+i+"的最短路径为:"+path[i]);
    }
    System.out.println("=====================================");
    for(int i = 1; i <= N; i++) {
        System.out.println("从1出发到" + i + "点的最短距离为:" + bestmin[i]);
    }
}
public static void main(String[] args) {
    //节点个数
      int N=5;
      int max=10000;

    int[][] distance=new int[N+1][N+1];
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(i == j) {
                distance[i][j] = 0;
            }else {
                distance[i][j] = max;
            }
        }
    }
    distance[1][2]=10;
    distance[1][4]=30;
    distance[1][5]=100;
    distance[2][3]=50;
    distance[3][5]=10;
    distance[4][5]=60;
    distance[4][3]=20;
    Dijkstra(N,distance);
}