Backtracking / activity scheduling maximum compatible activities

• The arrangement of activities
• n Activities need to use 1 Two mutually exclusive resources , Every activity has 1 Start time and 1 There will be conflicts between the two introductions , Find the maximum number of compatible activities
• What is compatibility / Incompatible activities ：
• Activity number 1 2 3 4
• Starting time 1 2 4 6
• End time 3 5 8 9
• The final end time of the activity is latest=0 Total compatible activities compatibleSum=0
• 0_{1, No activity ,1}3,latest=3, Activities 1; Activities 2 Demand from 2 Start , Are not compatible , Eliminate it ;3_{4, No activity ;4}8,latest=8, Activities 3; Activities 4 Demand from 6 Start , Are not compatible , Eliminate it
• The problem of activity arrangement itself is 1 A permutation problem , Find out 1 After permutations, you need to determine whether the activities represented by the permutation tree are compatible , The arrangement with the most compatible activities is the arrangement with the most compatible activities
• 1. Use the recursive algorithm of the permutation tree to get the active permutation first
• backtracking ： There will be a return - Node extension rules , Depth first search of the solution space tree in the process of pruning , Pruning function has constraint function , Bounded functions , There are two kinds of solution space trees: subset tree and permutation tree
• Solve the space tree / Number of subsets ： Meet the required subset , Subset of elements ; The branch represents a choice or no choice
• Solve the space tree / Permutation tree ： Achieve the required arrangement , All the elements are in ; Put that element in the 1 position , Put that element in the 2 position , By analogy
• Pruning function / Constraint function ： Decide whether to access the next node , Subtree does not satisfy the constraint ,
• Pruning function / Bounded functions ： Decide whether to access the subtree below , Subtree can not get the desired solution , Find the maximum using the upper bound function , Find the minimum using the lower bound function

package xcrj.kchalgorithm.backtracking;

import java.util.Arrays;

/** *  The arrangement of activities  * n Activities need to use 1 Two mutually exclusive resources , Every activity has 1 Start time and 1 There will be conflicts between the two introductions , Find the maximum number of compatible activities  * <p> *  What is compatibility / Incompatible activities ： *  Activity number  1 2 3 4 *  Starting time  1 2 4 6 *  End time  3 5 8 9 *  The final end time of the activity is latest=0  Total compatible activities compatibleSum=0 * 0~1, No activity ,1~3,latest=3, Activities 1; Activities 2 Demand from 2 Start , Are not compatible , Eliminate it ;3~4, No activity ;4~8,latest=8, Activities 3; Activities 4 Demand from 6 Start , Are not compatible , Eliminate it  * <p> * <p> *  The problem of activity arrangement itself is 1 A permutation problem , Find out 1 After permutations, you need to determine whether the activities represented by the permutation tree are compatible , The arrangement with the most compatible activities is the arrangement with the most compatible activities  *  The formation process of the permutation tree ： Select the first i Parent node formed after elements , The child node of the parent node , Through the parent node i And the j Element exchange , Take turns to j Put the first element in the second i position , Form child nodes  * <p> *  backtracking ： There will be a return - Node extension rules , Depth first search of the solution space tree in the process of pruning , Pruning function has constraint function , Bounded functions , There are two kinds of solution space trees: subset tree and permutation tree  *  Solve the space tree / Number of subsets ： Meet the required subset , Subset of elements ; The branch represents a choice or no choice  *  Solve the space tree / Permutation tree ： Achieve the required arrangement , All the elements are in ; Put that element in the 1 position , Put that element in the 2 position , By analogy  *  Pruning function / Constraint function ： Decide whether to access the next node , Subtree does not satisfy the constraint , *  Pruning function / Bounded functions ： Decide whether to access the subtree below , Subtree can not get the desired solution , Find the maximum using the upper bound function , Find the minimum using the lower bound function  */
public class ActivityArrange {
    
    static class Activity {
    
        private int start;
        private int end;

        public Activity() {
    
        }

        public Activity(int start, int end) {
    
            this.start = start;
            this.end = end;
        }

        public int getStart() {
    
            return start;
        }

        public void setStart(int start) {
    
            this.start = start;
        }

        public int getEnd() {
    
            return end;
        }

        public void setEnd(int end) {
    
            this.end = end;
        }
    }

    //  Do not use subscripts 0, The subscript is the unique number of the activity 
    static Activity[] activities = {
    new Activity(0, 0), new Activity(1, 3), new Activity(2, 5), new Activity(4, 8), new Activity(6, 9)};

    /* Solving process */
    //  Number of activities 
    static int n = 3;
    //  Arrangement of activities ,+1 Subscript 0 Don't use 
    static int[] xs = {
    0, 1, 2, 3};
    //  The final end time of the activity 
    static int latest;
    //  Number of compatible activities 
    static int compatibleSum;

    /* Result display */
    //  Optimal activity arrangement ,+1 Subscript 0 Don't use 
    static int[] optimalXs = new int[n + 1];
    //  Maximum number of compatible activities 
    static int maxCompatibleSum;

    /** * */
    public static void deepFirstSearch(int i) {
    
        //  Reach the leaf node , Because the root node is (0,0), So reaching the leaf node is i>n
        if (i > n) {
    
            //  If the result is better, keep 
            if (compatibleSum > maxCompatibleSum) {
    
                maxCompatibleSum = compatibleSum;
                //  Subscript 0 Don't use 
                for (int j = 1; j <= n; j++) {
    
                    optimalXs[j] = xs[j];
                }
            }
        }
        //  Reach the non leaf node , Generate i All child node activities of the node xs[j]（j from i Start ）
        else {
    
            //  Subscript 0 Don't use 
            for (int j = i; j <= n; j++) {
    
                //  For the convenience of backtracking , preservation 
                int compatibleSumTemp = compatibleSum;
                int latestTemp = latest;
                // xs[j] Is the number of the activity , Determine if the activity is compatible 
                if (activities[xs[j]].start >= latest) {
    
                    compatibleSum++;
                    latest = activities[xs[j]].end;
                }
                // ！ In exchange for , Select the first i Parent node formed after elements , The child node of the parent node , Through the parent node i And the j Element exchange , Take turns to j Put the first element in the second i position , Form child nodes 
                int temp = xs[i];
                xs[i] = xs[j];
                xs[j] = temp;
                //  The first i+1 Layer selection activity xs[j]（ from i+1 Start ） As nodes , Depth first traversal operation child node 
                deepFirstSearch(i + 1);
                //  In exchange for 
                int temp2 = xs[i];
                xs[i] = xs[j];
                xs[j] = temp2;
                //  to flash back , Cancel the i Layer selection of activities 
                compatibleSum = compatibleSumTemp;
                latest = latestTemp;
            }
        }
    }

    public static void main(String[] args) {
    
        // 1, From activities 1 Start 
        deepFirstSearch(1);

        System.out.println(" Maximum number of compatible activities :" + maxCompatibleSum);
    }
}