贪心算法(活动安排问题)

使用贪心算法的条件

    1.贪心选择性质：即所求问题的最优解可以通过一系列局部最优的选择来达到。
    2.最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题有最优子结构性质

活动安排问题：

有11个活动，活动按照结束时间的非递减排序如下：
        i  1  2  3  4  5  6  7  8  9  10  11
start[i]   1  3  0  5  3  5  6  8  8  2   12
finish[i]  4  5  6  7  8  9  10 11 12 13  14

思路：

1.需要先选定你的贪心的准则，是尽量活动安排的多，那么就以结束时间为基准，谁最先结束就先安排哪个活动
 
2.因为活动已经按照结束时间排序了，所以当前一个活动的结束时间与后一个活动的开始时间无冲突，就安排这个活动。

具体实现：

package 中级;
public class 贪心算法活动安排问题 {
    //贪心算法总是做出在当前看来是最好的选择
    public static void main(String[] args) {
        //开始时间数组
        int[] start = {1,3,0,5,3,5,6,8,8,2,12};
        //结束时间数组
        int[] end = {4,5,6,7,8,9,10,11,12,13,14};
        //创建一个数组存储是否安排活动
        boolean[] arrange = new boolean[11];
        //遍历数组，判断那些需要安排，安排的规则是按照顺序，没有相交的部分就安排
        arrange[0] = true;
        for(int i=1,j = 0;i<start.length;i++){
            //如果前一个的结束时间比后一个的开始时间小。则安排下去
            if(end[j] < start[i]){//符合要求
                arrange[i] = true;
                j = i;//如果成立，则j就是下一个作为参考的时间
            }else{
                arrange[i] = false;
            }
        }
        System.out.print("安排的活动有：");
        for(int i=0;i<arrange.length;i++){
            if(arrange[i] == true){
                System.out.print(i+",");
            }
        }
    }
}

• 1

总结：

1.这个问题用贪心算法是否能解决
 
2.如果能够使用贪心算法，那么贪心的准则是什么？（活动的问题的贪心准则就是活动的数量）
 
3.根据贪心的准则，明确需要进行判断的依据是什么？（活动安排问题，想要多的活动，就判断活动的结束时间，越早结束，安排的节目更多）