Greedy Algorithm (1)-Classic Greedy Algorithm

Table of Contents

1. Event arrangement issues

2. Optimal loading problem

3. Fraction knapsack problem

4. Multi-machine scheduling problem

1. Event Arrangement Issues

1. Strategy

Activity scheduling problem: There is a set of n activities E={1,2,…,n}, and each activity i has a starting time for using the resource $s_i$ and an end time $f_i$ , and $s_i<f_i$ . If activity i is selected then it is within the time interval $[s_i,f_i)$ How to choose the most activity plans within a limited time to occupy resources within a limited time.

Solution: Greedy algorithm with end time priority.

(1) If activity i and activity j are compatible, assuming activity i is before activity j, then there must be $f_i\leqslant s_j$ .

(2) According to $f_i$ sequence pair $f_i$ and $s_i$ Sort at the same time to ensure that the two correspond. Sorting can use quick sort, merge sort and heap sort. The complexity is O(nlogn).

(3) The first activity $f_i$ is the smallest, so Enter the event schedule, if other exists $s_j\geqslant f_i$ , then i=j, mobile activity arrangement.

Given an activity sequence $i,s_i,f_i$ Relationship:

2. Code

//Activity Arrangement
import java.util.Scanner;
public class activityarrangement {
   public static void main(String[] args)
   {
        int n=new Scanner(System.in).nextInt();
        int s[]=new int[n];
        int f[]=new int[n];
        for(int i=0;i<n;i + + )
            s[i]=new Scanner(System.in).nextInt();
        for(int i=0;i<n;i + + )
            f[i]=new Scanner(System.in).nextInt();
        quickSort(f,s, 0, n-1);
        GreedySelector(s,f);
   }
   public static void GreedySelector(int s[],int f[])
   {
        System.out.println(s[0] + " " + f[0]);
        int j=0;
        for(int i=1;i<s.length;i + + )
        {
            if(s[i]>=f[j])
            {
                System.out.println(s[i] + " " + f[i]);
                j=i;
            }
        }
   }

2. Optimal loading problem

1. Strategy

There is a batch of containers to be loaded onto a ship with a load of c. The weight of container i is $w_i$ , requiring that as many containers as possible be loaded onto ships without restrictions on loading volume.

Using a greedy algorithm, the container with the lightest weight is loaded first until the ship’s load cannot continue to load the container.

Sorting methods can use quick sort, sort and heap sort to reduce time complexity.

The constraints and objective function are as follows:

Example questions are as follows:

2. Code

//Optimal loading problem
public static void main(String []args)
   {
        int c=400;
        int weights[]={100,200,50,90,150,50,20,80};
        quickSort(weights,0,weights.length-1);
        System.out.println(load(weights,c));
   }
public static int load(int weights[],int c)
   {
        int tmp=c;
        for(int i=0;i<weights.length;i + + )
        {
            if(c>weights[i])
            {
                c-=weights[i];
            }
        }
        return tmp-c;
   }

3. Fractional knapsack problem

1. Strategy

Fractional knapsack problem: Based on the 0-1 knapsack problem, each item can be filled with a part, that is, the 0-1 knapsack problem requires solving the highest total value of the items contained on the basis of limited capacity.

Strategy: Agreedy algorithm that prioritizes the one with the highest unit weight value.

Create an array a (value per unit weight), use array a as the sorting basis, sort a, w, v arrays at the same time, and calculate the maximum total value that can be generated when the larger value of array a is given priority.

Example questions are as follows:

2. Code

(omit the sorting process)

//Fraction backpack problem
public class dividebackage {
public static void main(String[] args)
   {
        int n=3;
        int c=20;
        double w[]={18,15,10};
        double v[]={25,24,15};
        double a[]=new double[n];
        for(int i=0;i<n;i + + )
            a[i]=v[i]/w[i];

        quickSort(a,w,v,0,w.length-1);
        System.out.println(maximum(a,w,v,c));
        
            
   }
public static double maximum(double a[],double w[],double v[],int c)
   {
        double value=0;
        int weight=0;
        for(int i=a.length-1;i>=0;i--)
        {
            if((c-weight)>=w[i])
            {
                value + =v[i];
                weight + =w[i];
            }
            else
            {
                value + =v[i]*(c-weight)/w[i];
                break;
            }
        }
        return value;
   }
}

4. Multi-machine scheduling problem

1. Overview

Multi-machine scheduling problem: There are n independent jobs, which are processed by m identical machines. The processing time required for job i is $t_i$ , Each job can be processed on any machine, but it cannot be interrupted or split. Design an algorithm that enables n jobs to be processed by m machines in the shortest possible time.

Strategy: Carry out the greedy algorithm according to the longer task time, set five arrays of time, p, d, m, s (see the code comments below for definition). First, sort the time array and p array according to the task. Sorting in descending order of time (quick sort), the scheduling problem is a two-stage cycle of adding tasks and time lapse, until tasks are no longer added and the time that all machines still need to occupy is 0, then the scheduling problem is exited.

Add task: Traverse each machine. If the current machine m still needs to occupy 0 time, and there is still task i that needs to be added, then add task i to machine m, add one to the number of tasks done by machine m, and machine m executes the task. Add task i number.

Time passage: The time is moved back by one, and the required time of each task is reduced by one. If the time occupied by each machine is 0 and no new tasks are added, the scheduling problem is exited and the current time is returned. If the time occupied by machine i is 0, but there are still other machine tasks that have not been completed, the time occupied by machine i will no longer be reduced to avoid negative numbers.

The solution to the following example problem:

2. Code

//Multi-machine scheduling problem
public class multimachine {
   public static void main(String[] args)
   {
        int time[]={2,14,4,16,6,5,3}; //Time occupied by each task
        int p[]={1,2,3,4,5,6,7}; //task number
        int d[]={0,0,0}; //The amount of time the current machine still needs to occupy
        int m[]={0,0,0}; //Each machine performs several tasks
        int s[][]=new int[d.length][time.length]; //What tasks are performed by each machine
        //Reorder the time column and task number
        quickSort(time,p,0,time.length-1);
        //Output the total time of multi-machine scheduling
        deploy(time,p,d,s,m);
        //Output which tasks each machine performed
        for(int i=0;i<d.length;i + + )
        {
            for(int j=0;j<time.length;j + + )
            {
                if(s[i][j]==0)
                    break;
                System.out.print(s[i][j] + " ");
            }
            System.out.println("");
        }
   }
   public static void deploy(int time[],int p[],int d[],int s[][],int m[])
   {
        int tot=0;
        int c=0; //The total number of job sequences to be executed in sequence
        while(true)
        {
            //Enter the task and increase the time occupied by each machine
            for(int i=0;i<d.length;i + + )
            {
                if(d[i]==0 & amp; & amp;c<time.length)
                {
                    d[i] + =time[c];
                    s[i][m[i] + + ]=p[c + + ];
                }
            }
            tot + =1;
            int zero=0;
            //Increase the time by one to reduce the time occupied by each machine
            for(int i=0;i<d.length;i + + )
            {
                if(d[i]==0)
                    break;
                d[i]--;
                zero + =d[i];
            }
            //If each machine is 0 and no tasks are added, the schedule will be terminated.
            if(zero==0)
                break;
        }
        System.out.println(tot);
   }

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 56903 people are learning the system