贪心算法
在某一个标准下，优先考虑做满足标准的样本，最后考虑最不满足标准的样本，最终得到一个答案的算法，叫做贪心算法。
即，不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。
局部最优 -?-> 整体最优
例题
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。 给你每一个项目开始的时间和结束的时间(给你一个数 组，里面是一个个具体 的项目)，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回这个最多的宣讲场次。
- 哪个会议结束时间早，就先安排哪个会议
public class BestArrange {
public static class Program{
public int start;
public int end;
public Program(int start, int end){
this.start = start;
this.end = end;
}
}
public static class ProgramComparator implements Comparator<Program>{
@Override
public int compare(Program o1, Program o2) {
return o1.end - o2.end;
}
}
public static int bestArrange(Program[] programs, int start){
Arrays.sort(programs, new ProgramComparator());
int result = 0;
for (int i = 0; i < programs.length; i++) {
if(start <= programs[i].start){
result++;
start = programs[i].end;
}
}
return result;
}
}
贪心算法的在笔试时的解题套路
- 实现一个不依靠贪心策略的解法X，可以用最暴力的尝试
- 脑补出贪心策略A、贪心策略B、贪心策略C...
- 用解法X和对数器，去验证每一个贪心策略，用实验的方式得知哪个贪心策略正确
- 不要去纠结贪心策略的证明
给定一组字符串，给定使整体字典序和最小的方法。
- 比较字符串a和b方法，比较ab和ba的字典序，采取字典序较小的顺序。
public class LowestLexicography {
public static class MyComparator implements Comparator<String>{
@Override
public int compare(String a, String b){
return (a + b).compareTo(b + a);
}
}
public static String lowestString(String[] strs){
if(strs == null || strs.length == 0){
return "";
}
Arrays.sort(strs, new MyComparator());
String res = "";
for (int i = 0; i < strs.length; i++) {
res += strs[i];
}
return res;
}
}
- 证明方法，比较策略具有传递性
- 符合结合律，即 ab <= ba; bc <= cb --> ac <= ca。令klength(a) = m(a),表示数字向左位移length(a)位。
- 将字符串看成是k进制的数，
a.b = a * m(b) + b，故，条件为：
a * m(b) + b <= b * m(a) + a; 1
b * m(c) + c <= c *m(b) + b； 2 - 开始推理：
(1 - b)c : ac * m(b) <= bc * m(a) + ac - bc
(2 - b) * a : abm(c) + ac - ab <= ac * m(b)
--> ab * m(c) + ac - ba <= bc * m(a) + ac - bc
即：a * m(c) + c <= c*m(a) + a
- 证明按上述比较方法得到的字符串，交换任意两个字符ab（有ab < ba），将得到更大的字典序。
- 当a和b挨着的，（ab < ba）得证。
- 当a和b不挨着，.........
- 证明交换三个字符，得到更大的字典序。......
贪心策略在实现时，经常用到的技巧：
- 根据某标准建立一个比较器来排序
- 根据某标准建立一个比较器来组成堆
贪心算法3：
一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。
一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。
输入一个数组，返回分割的最小代价。
- 哈夫曼编码问题
public class LessMoneySplitGold {
public static int lessMoney(int[] arr){
PriorityQueue<Integer> pQ = new PriorityQueue<>();
for (int i = 0; i < arr.length; i++) {
pQ.add(arr[i]);
}
int sum = 0;
int cur = 0;
while(pQ.size() > 1){
cur = pQ.poll() + pQ.poll();
sum += cur;
pQ.add(cur);
}
return sum;
}
}
贪心算法4：ipo
输入：
正数数组costs
正数数组profits
正数k
正数m
含义： costs[i]表示i号项目的花费
profits[i]表示i号项目在扣除花费之后还能挣到的钱(利润)
k表示你只能串行的最多做k个项目
m表示你初始的资金
说明：
你每做完一个项目，马上获得的收益，可以支持你去做下一个项目。
输出： 你最后获得的最大钱数。
- 方法，将花费放进比较花费的小根堆内，
- 将花费小于资金的项弹出，放入比较利润的大根堆内，大根堆的根即为每次要做的项目。
- 做完项目后，资金变大，看小根堆里还有哪些项目可以弹出。
