Java贪心算法求解多机调度问题

朴灿烈づ我的快乐病毒、 2021-10-23 06:45 319阅读 0赞

问题描述:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Mzg4NzM0_size_16_color_FFFFFF_t_70]  
贪心算法

package 贪心;
    
    import java.util.*;
    
    public class Greedy2 {
        public static void main (String[] args) {
            int[] a = {5, 6, 3, 2, 8, 8 ,9};
            System.out.println("最优解"+greedy(a,3));
            //运行结果
            //将机器1从0到9分配给作业7
            //将机器2从0到8分配给作业5
            //将机器3从0到8分配给作业6
            //将机器3从8到14分配给作业2
            //将机器2从8到13分配给作业1
            //将机器1从9到12分配给作业3
            //将机器1从12到14分配给作业4
            //最优解14
        }
    
        private static int greedy (int[] arr, int m) {
            int n = arr.length;
            int sum = 0;
            if (n <= m) {
                for (int i = 0; i < n; i++) {
                    if (sum < arr[i]) {
                        sum = arr[i];
                    }
                }
                System.out.println("为每一台机器分工一个作业");
                return sum;
            }
            List<Job> jobs = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                Job job = new Job(i + 1, arr[i]);
                jobs.add(job);
            }
            Collections.sort(jobs);
            LinkedList<Machine> machines = new LinkedList<>();
            for (int i = 1; i <= m; i++) {
                Machine machine = new Machine(i, 0);
                machines.add(machine);
            }
            for (int i = 0; i < n; i++) {
                Collections.sort(machines);
                Machine mac =machines.peek();
                System.out.println("将机器" + mac.getId() + "从" + mac.getAvaile() + "到" + (mac.getAvaile() + jobs.get(i).getTime()) + "分配给作业" + jobs.get(i).getId());
                int a = mac.getAvaile() + jobs.get(i).getTime();
                mac.setAvaile(a);
    
                sum = a;
    
            }
    
            return sum;
        }
    }
    
    class Job implements Comparable {
        private int id;
        private int time;
    
        public Job (int id, int time) {
            this.id = id;
            this.time = time;
        }
    
        public int getId () {
            return id;
        }
    
        public void setId (int id) {
            this.id = id;
        }
    
        public int getTime () {
            return time;
        }
    
        public void setTime (int time) {
            this.time = time;
        }
    
        @Override
        public int compareTo (Object o) {
            int otherTime = ((Job) o).getTime();
            if (this.time < otherTime) return 1;
            if (this.time == otherTime) return 0;
            return -1;
        }
    }
    
    class Machine implements Comparable {
        private int id;
        private int availe;
    
    
        public Machine (int id, int availe) {
            this.id = id;
            this.availe = availe;
        }
    
        public int getId () {
            return id;
        }
    
        public void setId (int id) {
            this.id = id;
        }
    
        public int getAvaile () {
            return availe;
        }
    
        public void setAvaile (int availe) {
            this.availe = availe;
        }
    
        @Override
        public int compareTo (Object o) {
            int otherTime = ((Machine) o).getAvaile();
            if (this.availe < otherTime) return -1;
            if (this.availe == otherTime) return 0;
            return 1;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2Mzg4NzM0_size_16_color_FFFFFF_t_70]: /images/20211023/b667639a12bf4e76acb7c8c3445c41c3.png