贪心算法

引：上次看到过钟华老师的一个基于贪心算法的毕业设计，一直很好奇，今天终于能看看它了，只是知其然，不知所以然。

贪心算法总说

贪心算法在每一步都会做出看起来是最佳的选择，也就是说会做出局部最优的选择，希望以此能够得到最优解。

活动选择问题

贪心选择

我们要选择这样一个活动，选出它之后身下的资源能够被尽量多的其他任务所用，即选择最早结束的活动。

递归贪心算法

算法思路：用两个数组s和f表示活动的开始和结束时间。下表k是我们要求解的子问题，以及问题规模n，代码如下：

import java.util.ArrayList;
import java.util.List;

public class ActivitySelector {
public int[] s = new int[]{1,3,0,5,3,5,6,8,8,2,12};
public int[] f = new int[]{4,5,6,7,9,9,10,11,12,14,16};
public List<Integer> list = new ArrayList<>();
public void recursiveActivitySelector(int[] s, int[] f,int k,int n){
if(list.size()==0){
list.add(1);
}
int m = k+1;
while (m<n && s[m]<f[k]){
m = m+1;
}
if(m<n){
list.add(m+1);
recursiveActivitySelector(s, f, m, n);
} else {
return ;
}		
}
public static void main(String[] args) {
ActivitySelector activitySelector = new ActivitySelector();

activitySelector.recursiveActivitySelector(activitySelector.s, activitySelector.f, 0, activitySelector.f.length);
for (Integer i : activitySelector.list) {
System.out.println(i);
}
}
}

迭代贪心算法

这个过程是假设输入活动的结束时间是已经排好序的，代码如下：

import java.util.ArrayList;
import java.util.List;

public class GreedyActivitySelector {
public int[] s = new int[]{1,3,0,5,3,5,6,8,8,2,12};
public int[] f = new int[]{4,5,6,7,9,9,10,11,12,14,16};
public List<Integer> list = new ArrayList<>();
public void greedActivitySelector(int[] s,int[] f){
int n = s.length;
list.add(1);
int k = 1;
for (int m = 1; m < n; m++) {
if(s[m]>=f[k]){
list.add(k);
k = m;
}
}
}
public static void main(String[] args) {
ActivitySelector activitySelector = new ActivitySelector();

activitySelector.recursiveActivitySelector(activitySelector.s, activitySelector.f, 0, activitySelector.f.length);
for (Integer i : activitySelector.list) {
System.out.println(i);
}
}
}

贪心算法原理

设计贪心算法的过程

1. 确定问题的最优子结构
2. 设计一个递归算法
3. 证明一个贪心选择，则只剩下一个子问题
4. 证明贪心选择总是安全的
5. 设计一个递归算法实现贪心策略
6. 将递归算法转换为迭代算法

证明一个贪心算法是否能求解一个最优化问题？具有下面性质就ok？

1. 贪心选择性质

我们可以通过做出局部最优选择来构造全局最优解

1. 最优子结构

如果一个问题的最优解包含子问题的最优解

总结

一步一步慢慢贪心，和做人是一样的，但是总的来说还是要考虑全局的！！！