大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 算法起步之贪心算法

算法起步之贪心算法

关键词:算法起步贪心算法算法起步之贪心算法  阅读(746) 赞(15)

[摘要]本文主要是对算法起步之贪心算法的讲解,希望对大家学习算法起步之贪心算法有所帮助。

  我们前面介绍的动态规划算法是求解最优化问题的一种通用方法,但是对于很多的最优化问题是用动态规划有点小题大做了,我们可以使用贪心算法,贪心算法相比动态规划更简单,也更高效。它总是做出局部最优选择,希望这样可以得到全局的最有选择。所以这种方法不能保证得到最优解,但是很多问题却都可以用这种方法。我们先看一个活动选择的例子。

  假设我们有n个活动,只有一个教室,求在这个教室中一天最多可以举办多少活动(同一时间只能举办一个活动)。下面给出的是活动的开始时间跟结束时间。

  i序号 1 2 3 4 5 6 7 8 9 10 11

  s开始 1 3 0 5 3 5 6 8 8 2 12

  f结束 4 5 6 7 9 9 10 11 12 14 16

  动态规划解法:

  本来想这个用动态规划很简单,看了一下算法导论写的,只写了一个递归的算法,但是递归的效率太低,于是就想写自底向上的,写了一个简单的确发现自己想错了,于是在网上找了很多动态规划解活动选择的问题,都不太满意,都不是按照我想的那样,很多写的算法时间复杂度达到了n的三次方。今天又看了一遍题目,突然写了出来,虽然耽误了很多时间,但是我觉得这比网上其他给的答案还要快一点。

  public class DPActity {

  public void actity(){

  Scanner sc=new Scanner(System.in);

  int[][] map=new int[25][25];

  for (int i = 0; i < 11; i++) {

  map[sc.nextInt()][sc.nextInt()]=1;

  }

  for(int i=1;i<MAP.LENGTH;I++){ if(a b){ a,int max(int int public } System.out.println(map[0][24]); map[0][i]="max(map[0][i-1]," }else{ 1+map[0][j]); if(map[j][i]="=1){" j="0;j<=i;j++){" for(int>b){

  return a;

  }else{

  return b;

  }

  }

  public static void main(String[] args) {

  new DPActity()。actity();

  }

  }

  虽然这样写的感觉代码也不多,但是如果我们用贪心的做法你会发现非常简单,而且好理解。因为我们的数值倒是按照结束时间排序的,所以一直选择结束时间最短的则获得最优解。在这里选择结束时间最早的活动就是我们的决策点。而贪心算法关键就是在选择决策点上。顺便一提像01背包问题不能用贪心算法来解但是分数背包可以解决。

  public void greedy(int[]s,int[]f){

  int n=s.length;

  int k=1;

  for (int i = 2; i < n; i++) {

  if (s[i]>=f[k]) {

  k=i;

  }

  }

  System.out.println(k);

  }



相关评论