贪心算法

思想

所谓贪心算法，就是在走的每一步都不考虑后面的操作，即不考虑全局，只关注当下，即寻找局部最优解，因此贪心算法，并不能保证找到全局最优解。
实际上，贪心算法用得很少，除非在已知使用贪心算法能过找到最优解时使用。

贪心算法在作出每一步的决策之后，将不可改变

例子

• 有如下的一个任务序列{1,2,3,4,5},表示5个任务
• 有T = {5, 8, 4, 10, 3};, 表示执行这5个任务需要的时间
• 有D = {10, 15, 20, 18, 30};，表示这个5个任务期望完成的时间，这是一个时间点，即时刻，上面T表示的是一段时间，比如5分钟。

  需求

1. 如果所有的任务都执行，求出每个任务的延迟，以及最大的延迟。
2. 对于有延迟的任务，直接不执行，求出满足不延迟的任务序列

   实现(java)

   import java.util.Scanner;
   
   /**
    * @ClassName: GreedyMain
    * @Author: fanjiajia
    * @Date: 2019/3/4 下午8:44
    * @Version: 1.0
    * @Description: 贪心算法
    */
   public class GreedyMain {
   
       public  static void  main(String[] args) {
           Scanner scanner = new Scanner(System.in);
   //        System.out.print("请输入任务:n = ");
   //        int n = scanner.nextInt();
   //        System.out.println();
   //        int T[] = new int[n];
   //        int D[] = new int[n];
   //        System.out.println("请输入每个任务完成需要的时间:");
   //        for (int i = 0; i < n; i++) {
   //            T[i] = scanner.nextInt();
   //        }
   //        System.out.println("请输入每个任务希望完成的时间点:");
   //        for (int i = 0; i < n; i++) {
   //            D[i] = scanner.nextInt();
   //        }
           int n = 5;
           int[] T = {5, 8, 4, 10, 3};
           int[] D = {10, 15, 20, 18, 30};
           // 1. 对希望完成的任务进行排序，从小到大
           for (int i = 0; i < D.length; i++) {
               for (int j = 0; j < D.length - i -1; j++) {   // 因为i从0开始，确保最后一个
                   if (D[j] > D[j + 1]) {  // 这里有j+1，说明为什么上面-1
                       swap(D, j, j + 1);
                       swap(T, j, j + 1);
                   }
               }
           }
           // 2. 所有的任务都执行，求最大的延迟
           int maxDelayTime = 0;   // 最大的延迟时间
           int curTime = 0;    // 当前完成时间点
           int index = -1; // 记录是哪一个任务被延迟
           for (int i = 0; i < n; i++) {
               curTime += T[i];
               if (curTime > D[i]) { // 说明此任务需要延迟
                   if (curTime - D[i] > maxDelayTime) {
                       maxDelayTime = curTime - D[i];  // 更新最大延迟时间
                       index = i;
                   }
               }
           }
           System.out.println("当前任务序列第" + (index + 1) +"个的延迟最大,为:" + maxDelayTime);    // 这里排序了，下标不准确
   
           curTime = 0;
           // 3. 不满足的任务不执行，获取可以执行的任务
           for (int i = 0; i < n; i++) {
               curTime += T[i];
               if (curTime < D[i]) { // 说明此任务满足
                   System.out.print(i + " ");
               }
           }
       }
   
       /**
        * 交换数组中的两个元素
        * @param arr
        * @param i
        * @param j
        */
       private static void swap(int[] arr, int i, int j) {
           int temp = arr[i];
           arr[i] = arr[j];
           arr[j] = temp;
       }
   }

这里的操作并不严谨，因为数组排序后，序列发生改变，因此在实际的贪心算法中，多用对象表示。
很好的贪心算法是，背包问题，零钱找零问题，，，（详细见参考资料）

参考资料

https://www.cnblogs.com/xsyfl/p/6938642.html
https://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html
https://blog.csdn.net/cwh0908/article/details/80193312

最后

此致，敬礼