算法设计与分析-贪心法

算法设计与分析-贪心法,第1张

文章目录
    • 1 贪心法概述
      • 1.1 什么是贪心法
      • 1.2 贪心法求解的问题应具有的性质
      • 1.3 贪心法的一般求解过程
    • 2 求解活动安排问题
    • 3 求解背包问题
    • 4 求解最优装载问题
    • 5 求解田忌赛马问题
    • 6 求解多机调度问题
    • 7 哈夫曼编码
    • 8 求解流水作业调度问题

1 贪心法概述 1.1 什么是贪心法

​ 贪心法的基本思路是在对问题求解时总是做出在当前看来是最好的选择,也就是说贪心法不从整体最优上加以考虑,所做出的仅是在某种意义上的局部最优解。

​ 人们通常希望找到整体最优解,所以采用贪心法需要证明设计的算法确实是整体最优解或求解了它要解决的问题。

1.2 贪心法求解的问题应具有的性质

1 贪心选择性质

所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。

也就是说,贪心法仅在当前状态下做出最好选择,即局部最优选择,然后再去求解做出这个选择后产生的相应子问题的解。

2 最优子结构性质

​ 如果一个问题的最优解包含其子问题的最优解,则称此问题具有最优子结构性质。

​ 问题的最优子结构性质是该问题可用动态规划算法或贪心法求解的关键特征。

1.3 贪心法的一般求解过程

贪心法求解问题的算法框架如下:

SolutionType Greedy(SType a[],int n)
//假设解向量(x0,x1,…,xn-1)类型为SolutionType,其分量为SType类型
{  SolutionType x={}//初始时,解向量不包含任何分量
   for (int i=0;i<n;i++)	  //执行n步 *** 作
   {  SType xi=Select(a);	  //从输入a中选择一个当前最好的分量
      if (Feasiable(xi))	  //判断xi是否包含在当前解中
	 solution=Union(x,xi);	  //将xi分量合并形成x 
   }
   return x;			  //返回生成的最优解
}
2 求解活动安排问题

【问题描述】假设有一个需要使用某一资源的n个活动所组成的集合S,S={1,…,n}。该资源任何时刻只能被一个活动所占用,活动i有一个开始时间bi和结束时间ei(bi

​ 一旦某个活动开始执行,中间不能被打断,直到其执行完毕。若活动i和活动j有bi≥ej或bj≥ei,则称这两个活动兼容。

​ 设计算法求一种最优活动安排方案,使得所有安排的活动个数最多。

【问题求解】假设活动时间的参考原点为0。一个活动i(1≤i≤n)用一个区间[bi,ei)表示,当活动按结束时间(右端点)递增排序后,两个活动[bi,ei)和[bj,ej)兼容(满足bi≥ej或bj≥ei)实际上就是指它们不相交。

​ 用数组A存放所有的活动,A[i].b(1≤i≤n),存放活动起始时间,A[i].e存放活动结束时间。

例如,对于下表的n=11个活动(已按结束时间递增排序)A:

i1234567891011
开始时间130535688212
结束时间4567891011121315

产生最大兼容活动集合的过程:

活动1    √
活动2    x
活动3    x
活动4    √
活动5    x
活动6    x
活动7    x
活动8    √
活动9    x
活动10   x
活动11   √

4167. 活动安排 - AcWing题库

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  int n;
  Action[] a;
  boolean[] flag;  //标记选择的活动
  int maxSum = 0;

  void solve(){
    Arrays.sort(a,(o1, o2) -> { return o1.e-o2.e;}); //A[1..n]按活动结束时间递增排序
    int preEnd=0;  //前一个兼容活动的结束时间
    for (int i = 0; i < n; i++) {
      if (a[i+1].b>=preEnd){
        preEnd=a[i+1].e;
        maxSum++;
        flag[i+1]=true;
      }
    }
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int i = scanner.nextInt();
    Main activity = new Main();
    activity.n=i;
    activity.a=new Action[i+1];
    activity.a[0]=new Action();
    activity.flag=new boolean[i+1];
    for (int j = 0; j < i; j++) {
      activity.a[j+1]=new Action();
      activity.a[j+1].b= scanner.nextInt();
      activity.a[j+1].e= scanner.nextInt();
    }
    activity.solve();
    System.out.println(activity.maxSum);
  }
}

//活动
class Action {

  int b; //活动开始时间
  int e; //活动结束时间

}

【算法分析】算法的主要时间花费在排序上,排序时间为O(nlog2n),所以整个算法的时间复杂度为O(nlogn)。

【算法证明】通常证明一个贪心选择得出的解是最优解的一般的方法是,构造一个初始最优解,然后对该解进行修正,使其第一步为一个贪心选择,证明总是存在一个以贪心选择开始的求解方案。

​ 对于本问题,所有活动按结束时间递增排序,就是要证明:若X是活动安排问题A的最优解,X=X’∪{1},则X’是A’={i∈A:ei≥b1}的活动安排问题的最优解。

​ 首先证明总存在一个以活动1开始的最优解。

​ 如果第一个选中的活动为k(k≠1),可以构造另一个最优解Y,Y中的活动是兼容的,Y与X的活动数相同。

​ 那么用活动1取代活动k得到Y’,因为e1≤ek,所以**Y’中的活动是兼容的,即Y’**也是最优的,这就说明总存在一个以活动1开始的最优解。

当做出了对活动1的贪心选择后,原问题就变成了在活动2、…、n中找与活动1兼容的那些活动的子问题。亦即,如果X为原问题的一个最优解,则X'=X-{1}也是活动选择问题A'={i∈A|bi≥e1}的一个最优解。

​ 反证法:如果能找到一个A’的含有比X’更多活动的解Y’,则将活动1加入Y’后就得到A的一个包含比X更多活动的解Y,这就与X是最优解的假设相矛盾。

​ 因此,在每一次贪心选择后,留下的是一个与原问题具有相同形式的最优化问题,即最优子结构性质。

【例】 求解蓄栏保留问题。农场有n头牛,每头牛会有一个特定的时间区间[b,e]在蓄栏里挤牛奶,并且一个蓄栏里任何时刻只能有一头牛挤奶。

​ 现在农场主希望知道最少蓄栏能够满足上述要求,并给出每头牛被安排的方案。对于多种可行方案,输出一种即可。

解:牛的编号为1~n,每头牛的挤奶时间相当于一个活动,与前面活动安排问题不同,这里的活动时间是闭区间,例如[2,4]与[4,7]是交叉的,它们不是兼容活动。

​ 采用与求解活动安排问题类似的贪心思路,将所有活动这样排序:结束时间相同按开始时间递增排序,否则按结束时间递增排序。

​ 求出一个最大兼容活动子集,将它们安排在一个蓄栏中(蓄栏编号为1);如果没有安排完,再在剩余的活动再求下一个最大兼容活动子集,将它们安排在另一个蓄栏中(蓄栏编号为2),以此类推。

​ 也就是说,最大兼容活动子集的个数就是最少蓄栏个数。

i1234567
开始时间125841211
结束时间4579101315

三个子集

1346
15812
47913
27
211
515
5
4
10

3190 – Stall Reservations (poj.org)

超时。。。

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main {

  int n;  //牛数量
  int ans[];      //ans[i]表示第cows[i].no头牛的蓄栏编号
  Cow[] cows;
  int[] result;  //方便按顺序输出

  void solve() {
    ans = new int[n + 1];
    result = new int[n + 1];
    Arrays.sort(cows, new Comparator<Cow>() {
      @Override
      public int compare(Cow o1, Cow o2) {
        return (o1.e - o2.e == 0 ? (o1.b - o2.b) : o1.e - o2.e);
      }
    });
    int num = 1;  //畜栏编号
    for (int i = 1; i <= n; i++) {
      //第i头牛还没有安排蓄栏
      if (ans[i] == 0) {
        ans[i] = num;
        result[cows[i].no]=num;
        int preEnd = cows[i].e;
        for (int j = i + 1; j <= n; j++) {
          if (cows[j].b > preEnd && ans[j] == 0) {
            ans[j] = num;
            preEnd = cows[j].e;
            result[cows[j].no]=num;
          }
        }
        num++;
      }
    }
    System.out.println(--num);
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    Main main = new Main();
    main.n = n;
    main.cows = new Cow[n + 1];
    main.cows[0] = new Cow();
    for (int i = 1; i <= n; i++) {
      main.cows[i] = new Cow();
      main.cows[i].no=i;
      main.cows[i].b= scanner.nextInt();
      main.cows[i].e= scanner.nextInt();
    }
    main.solve();
    for (int i = 0; i < n; i++) {
      System.out.println(main.result[i+1]);
    }
  }

}

class Cow {

  int no;   //牛编号
  int b;    //开始时间
  int e;    //结束时间
}

按开始时间递增+优先队列

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {

  int n;  //牛数量
  int ans[];      //ans[i]表示第cows[i].no头牛的蓄栏编号
  Cow[] cows;

  void solve() {
    ans = new int[n + 1];
    result = new int[n + 1];
    Arrays.sort(cows, new Comparator<Cow>() {
      @Override
      public int compare(Cow o1, Cow o2) {
        return o1.b - o2.b;
      }
    });
    PriorityQueue<Cow> heap = new PriorityQueue<Cow>(n,new Comparator<Cow>() {
      @Override
      public int compare(Cow o1, Cow o2) {
        return o1.e - o2.e;
      }
    });
    int num = 1;  //畜栏编号
    heap.add(cows[1]);
    ans[cows[1].no] = num;
    for (int i = 2; i <= n; i++) {
      if (cows[i].b > heap.peek().e) {
        Cow cow = heap.poll();
        ans[cows[i].no] = ans[cow.no];
      } else {
        ans[cows[i].no] = ++num;
      }
      heap.add(cows[i]);
    }
    System.out.println(num);
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    Main main = new Main();
    main.n = n;
    main.cows = new Cow[n + 1];
    main.cows[0] = new Cow();
    for (int i = 1; i <= n; i++) {
      main.cows[i] = new Cow();
      main.cows[i].no = i;
      main.cows[i].b = scanner.nextInt();
      main.cows[i].e = scanner.nextInt();
    }
    main.solve();
    for (int i = 0; i < n; i++) {
      System.out.println(main.ans[i + 1]);
    }
  }

}

class Cow {

  int no;   //牛编号
  int b;    //开始时间
  int e;    //结束时间
}
3 求解背包问题

【**问题描述】**设有编号为1、2、…、n的n个物品,它们的重量分别为w1、w2、…、wn,价值分别为v1、v2、…、vn,其中wi、vi(1≤i≤n)均为正数。

有一个背包可以携带的最大重量不超过W。求解目标:在不超过背包负重的前提下,使背包装入的总价值最大(即效益最大化),与0/1背包问题的区别是,这里的每个物品可以取一部分装入背包。

贪心法-求解部分背包问题_松东路的博客-CSDN博客

P2240 【深基12.例1】部分背包问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

import java.util.Arrays;
import java.util.Scanner;
import java.text.DecimalFormat;

public class Main {

  double W;  //限重
  double V;  //max value
  int n;  //物品数量
  Goods[] goods;

  //求解背包问题并返回总价值
  void knap() {
    Arrays.sort(goods, (o1, o2) -> {
      return (o1.p - o2.p) < 0 ? 1 : -1;
    });  //按p降序排序
    int i = 0;
    while (i < n && goods[i].w <= W) {
      V += goods[i].v;
      W -= goods[i].w;
      i++;
    }
    if (i < n && W > 0) {
      V += W * goods[i].p;
    }
  }

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    Main bag = new Main();
    int n = scanner.nextInt();
    bag.n = n;
    bag.W = scanner.nextInt();
    bag.goods = new Goods[n];
    for (int i = 0; i < n; i++) {
      bag.goods[i] = new Goods(scanner.nextInt(), scanner.nextInt());
    }
    bag.knap();
    DecimalFormat format = new DecimalFormat("#.00");  //保留小数点后两位
    System.out.println(format.format(bag.V));
  }

}

class Goods {

  double w;
  double v;
  double p;  //p=v/w

  public Goods(double w, double v) {
    this.w = w;
    this.v = v;
    this.p = v / w;
  }
}
4 求解最优装载问题

【问题描述】有n个集装箱要装上一艘载重量为W的轮船,其中集装箱i(1≤i≤n)的重量为wi。

不考虑集装箱的体积限制,现要选出尽可能多的集装箱装上轮船,使它们的重量之和不超过W。

【问题求解】在回溯法篇讨论了简单装载问题,采用回溯法选出尽可能少的集装箱个数。这里的最优解是选出尽可能多的集装箱个数,并采用贪心法求解。

当重量限制为W时,wi越小可装载的集装箱个数越多,所以采用优先选取重量轻的集装箱装船的贪心思路。

对wi从小到大排序得到{w1,w2,…,wn},设最优解向量为x={x1,x2,…,xn},显然,x1=1,则x’={x2,…,xn}是装载问题w’={w2,…,wn},W’=W-w1的最优解,满足贪心最优子结构性质。

代码略。

【算法分析】算法的主要时间花费在排序上,时间复杂度为O(nlog2n)。

5 求解田忌赛马问题

【问题描述】二千多年前的战国时期,齐威王与大将田忌赛马。双方约定每人各出300匹马,并且在上、中、下三个等级中各选一匹进行比赛,由于齐威王每个等级的马都比田忌的马略强,比赛的结果可想而知。现在双方各n匹马,依次派出一匹马进行比赛,每一轮获胜的一方将从输的一方得到200银币,平局则不用出钱,田忌已知所有马的速度值并可以安排出场顺序,问他如何安排比赛获得的银币最多。

​ 输入:输入包含多个测试用例,每个测试用例的第一行正整数n(n≤1000)马的数量,后两行分别是n个整数,表示田忌和齐威王的马的速度值。输入n=0结束。

​ 输出:每个测试用例输出一行,表示田忌获得的最多银币数。

输入样例:
3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0
样例输出:
200
0
0

【问题求解】田忌的马速度用数组a表示,齐威王的马速度用数组b表示,将a、b数组递增排序。采用常识性的贪心思路,分以下几种情况:

(1)田忌最快的马比齐威王最快的马快即a[righta]>b[rightb],则两者比赛(两个最快的马比赛),田忌赢。因为此时田忌最快的马一定赢,而选择与齐威王最快的马比赛对于田忌来说是最优的。

(2)田忌最快的马比齐威王最快的马慢即a[righta]

(3)田忌最快的马与齐威王最快的马的速度相同即a[righta]=b[rightb],又分为以下3种情况:

​ ① 田忌最慢的马比齐威王最慢的马快即a[lefta]>b[leftb],则两者比赛(两个最慢的马比赛),田忌赢。因为此时齐威王最慢的马一定输,而选择与田忌最慢的马比赛对于田忌来说是最优的。

​ ② 田忌最慢的马比齐威王最慢的马慢,并且田忌最慢的马比齐威王最快的马慢,即a[lefta]≤b[leftb]且a[lefta]

​ ③ 其他情况,平局。

上述过程看出每种情况对于田忌来说都是最优的,因此最终获得的比赛方案也一定是最优的。

P1650 田忌赛马 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

2287 – Tian Ji – The Horse Racing (poj.org)

import java.util.Arrays;
import java.util.Scanner;

public class Main {

  int n;  //马的数量
  int[] a;  //田忌的马速度值
  int[] b;  //齐王的马速度值
  int ans;

  void solve() {
    Arrays.sort(a);
    Arrays.sort(b);
    int la = 0, lb = 0, ra = n - 1, rb = n - 1;
    while (la <= ra) {
      if (a[ra] > b[rb]) {
        ans += 200;
        ra--;
        rb--;
      } else if (a[ra] < b[rb]) {
        la++;
        rb--;
        ans -= 200;
      } else {
        if (a[la] > b[lb]) {
          ans += 200;
          la++;
          lb++;
        } else {  //用田忌最慢的马与齐威王最快的马比赛
          if (a[la] < b[rb]) {
            ans -= 200;
          }
          la++;
          rb--;
        }
      }
    }
  }

  public static void main(String[] args) {
    Main main = new Main();
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    main.n = n;
    main.a = new int[n];
    main.b = new int[n];
    for (int i = 0; i < n; i++) {
      main.a[i] = scanner.nextInt();
    }
    for (int i = 0; i < n; i++) {
      main.b[i] = scanner.nextInt();
    }
    main.solve();
    System.out.print(main.ans);
  }
}

【算法分析】算法的主要时间花费在排序上,时间复杂度为O(nlog2n)。

6 求解多机调度问题

【问题描述】设有n个独立的作业{1,2,…,n},由m台相同的机器{1,2, …,m}进行加工处理,作业i所需的处理时间为ti(1≤i≤n),每个作业均可在任何一台机器上加工处理,但未完工前不允许中断,任何作业也不能拆分成更小的子作业。

多机调度问题要求给出一种作业调度方案,使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。

【问题求解】贪心法求解多机调度问题的贪心策略是最长处理时间作业优先,即把处理时间最长的作业分配给最先空闲的机器,这样可以保证处理时间长的作业优先处理,从而在整体上获得尽可能短的处理时间。

按照最长处理时间作业优先的贪心策略,当m≥n时,只要将机器i的[0,ti)时间区间分配给作业i即可;

当m

import java.util.Arrays;
import java.util.PriorityQueue;

public class DiaoDu {

  //问题表示
  int n = 7;
  int m = 3;
  Node A[] = {new Node(1, 2), new Node(2, 14), new Node(3, 4), new Node(4, 16), new Node(5, 6),
      new Node(6, 5), new Node(7, 3)};

  void solve() {
    Node e;
    if (n <= m) {
      System.out.println("为每一个作业分配一台机器\n");
      return;
    }
    Arrays.sort(A, (o1, o2) -> {
      return o2.t - o1.t;
    });      //按t递减排序
    PriorityQueue<Node> qu = new PriorityQueue<>((o1, o2) -> {
      return o1.t - o2.t;
    });  //小根堆
    for (int i = 0; i < m; i++)    //先分配m个作业,每台机器一个作业
    {
      A[i].mno = i + 1;      //作业对应的机器编号
      System.out.println(
          "  给机器" + A[i].mno + "分配作业" + A[i].no + ",执行时间为" + A[i].t + ",占用时间段:[0," + A[i].t + "]");
      qu.add(A[i]);
    }
    for (int j = m; j < n; j++)    //分配余下作业
    {
      e = qu.peek();
      qu.poll();    //出队e
      System.out.println(
          "给机器" + e.mno + "分配作业" + A[j].no + ",执行时间为" + A[j].t + ",占用时间段:[" + e.t + "," + (e.t
              + A[j].t) + "]");
      e.t += A[j].t;
      qu.add(e);      //e进队
    }
  }

  public static void main(String[] args) {
    DiaoDu diaoDu = new DiaoDu();
    diaoDu.solve();
  }
}



class Node        //优先队列结点类型
{

  int no;          //作业序号
  int t;          //执行时间
  int mno;          //机器序号

  public Node(int no, int t) {
    this.no = no;
    this.t = t;
  }
}

【算法分析】排序的时间复杂度为O(nlog2n),两次for循环的时间合起来为O(n),所以本算法的时间复杂度为O(nlog2n)。

7 哈夫曼编码

3531. 哈夫曼树 - AcWing题库

public class Main {
    public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
      return o1 - o2;
    });
    for (int i = 0; i < n; i++) {
      queue.add(scanner.nextInt());
    }
    int ans = 0;
    while (queue.size()>1) {
      Integer a = queue.poll();
      Integer b = queue.poll();
      queue.add(a + b);
      ans += a + b;
    }
    System.out.println(ans);
  }
}
8 求解流水作业调度问题

【问题描述】有n个作业(编号为1~n)要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工,然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi(1≤i≤n)。

​ 流水作业调度问题要求确定这n个作业的最优加工顺序,使得从第一个作业在机器M1上开始加工,到最后一个作业在机器M2上加工完成所需的时间最少。可以假定任何作业一旦开始加工,就不允许被中断,直到该作业被完成,即非优先调度。

4170. 加工生产调度 - AcWing题库

#10003. 「一本通 1.1 例 4」加工生产调度 - 题目 - LibreOJ (loj.ac)

【问题求解】采用归纳思路。当只有一个作业(a1,b1),显然最少时间Tmin=a1+b1。

当有两个作业(a1,b1)和(a2,b2)时,若(a1,b1)在前(a2,b2)在后执行:

Tmin=a1+b1+a2+b2-min(a2,b1)

若(a2,b2)在前(a1,b1)在后执行,可以求出最少时间

        Tmin=a2+b2+a1+b1-min(b2,a1)

将两种执行顺序合并起来有:

      Tmin=a1+b1+a2+b2-max(min(a2,b1),min(a1,b2))

由此可以得到一个贪心的性质:
对于(a1,b1)和(a2,b2)中的元素
若min(a1,b2)≤min(a2,b1),则(a1,b1)放在(a2,b2)前面;
反之,若min(a2,b1)≥min(a1,b2) (a2,b2)放在(a1,b1)前面。

让(a,b)中a比较小的尽可能先执行,(a,b)中b比较小的尽可能后执行!

Johnson贪心算法。其步骤如下:

(1)把所有作业按M1、M2的时间分为两组,a[i]≤b[i]对应第1组N1,a[i]>b[i]对应第2组N2。

(2)将N1的作业按a[i]递增排序,N2的作业按b[i]递减排序。

(3)按顺序先执行N1的作业,再执行N2的作业,得到的就是耗时最少的最优调度方案。

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class Main {


  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int n = scanner.nextInt();
    Item[] items = new Item[n];
    List<Item> l1 = new LinkedList<>();
    List<Item> l2 = new LinkedList<>();
    for (int i = 0; i < n; i++) {
      items[i] = new Item();
      items[i].no = i + 1;
      items[i].a = scanner.nextInt();
    }
    for (int i = 0; i < n; i++) {
      items[i].b = scanner.nextInt();
      if (items[i].a < items[i].b) {
        l1.add(items[i]);
      } else {
        l2.add(items[i]);
      }
    }
    l1.sort((o1, o2) -> {
      return o1.a - o2.a;
    });
    l2.sort((o1, o2) -> {
      return o2.b - o1.b;
    });
    int f1 = 0;
    int f2 = 0;
    l1.addAll(l2);
    for (int i = 0; i < l1.size(); i++) {
      f1 += l1.get(i).a;
      f2 = Math.max(f1, f2) + l1.get(i).b;
    }
    System.out.println(f2);
    for (Item item : l1) {
      System.out.print(item.no + " ");
    }
  }
}

class Item {

  int no;
  int a;
  int b;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/1325721.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-06-12
下一篇 2022-06-12

发表评论

登录后才能评论

评论列表(0条)

保存