贪心算法面试题

001什么是贪心算法？

贪心算法，看着这个名字贪心、贪婪这两字的内在含义最为关键。这就好像一个贪婪的人，他事事都想要眼前看到最好的那个，看不到长远的东西，也不为最终的结果和将来着想，贪图眼前局部的利益最大化，有点走一步看一步的感觉。
贪心算法是寻找最优解问题的常用方法，这种方法模式一般将求解过程分成若干个步骤，但每个步骤都应用贪心原则，选取当前状态下最好/最优的选择（局部最有利的选择），并以此希望最后堆叠出的结果也是最好/最优的解。
贪心算法的基本步骤：
步骤1：从某个初始解出发；
步骤2：采用迭代的过程，当可以向目标前进一步时就根据局部最优策略，得到一部分解，缩小问题规模；
步骤3：将所有解综合起来；

002找零钱问题

假设你开了间小店，不能电子支付，钱柜里的货币只有 25 分、10 分、5 分和 1 分四种硬币，如果你是售货员且要找给客户 41 分钱的硬币，如何安排才能找给客人的钱既正确且硬币的个数又最少？
这里我们需要明确的几个点：
1.货币只能25分、10分、5分和1分四种硬币；
2.找给客户41分钱的硬币；
3.硬币最少化。
思考，能使用我们今天学到的贪婪算法吗？怎么做？（回顾下贪婪算法的步骤）
1.找给顾客钱sun_money=41分钱，可选择的是25分，10分，5分和1分四种硬币。能找25分的就不找10分的原则，初次先找给顾客25分；
2.还差顾客sum_money=41-25=16。然后从25分、10分、5分和1分四种硬币选取局部最优的给顾客，也就是选10分的，此时sum_money=16-10=6。重复迭代过程，还需要sum_money=6-5=1,sum_money=1-1=0。至此，顾客收到零钱，交易结束；
3.此时41分，分成1个25分，1个10分，1个5分，1个1分，总共四枚硬币。

public static void main(String[] args){
    // 不断尝试每种硬笔
    int num25, num10, num5, num1; 
    num25=num10=num5=num1=0;
    while(money >= 25){
        num25++;
        money -= 25;
    } 
    while(money >= 10){
        num10++;
        money -= 10;
    }
    while(money >=5){
        num5++;
        money -=5;
    }
    while(money >=1){
        num1++;
        money -= 1;
    }
    System.out.println("25分有 "+num25);
    System.out.println("10分有 "+num10);
    System.out.println("5分有 "+num5);
    System.out.println("1分有 "+num1);
    return 0;
}

003会议安排问题

如何在有限的时间内有召开多个会议，要求任何两个会议不能同时进行。
如下表是会议时间表

通过会议时间表可得到比较直观的下图

我们需要选出最多的不相交的时间段，可以尝试以下的贪心策略：
(1)每次从剩下未安排会议中选出最早开始且与已安排会议不冲突的会议；
(2)每次从剩下未安排会议中选出持续时间最短且与已安排会议不冲突的会议；
(3)每次从剩下未安排会议中选出最早结束且与已安排会议不冲突的会议；
我们简单地分析一下：
如果选择最早开始时间，如果会议持续时间很长，假如8点开始，却要持续12小时，这样每天只能安排一个会议，肯定不合理；如果选择持续时间最短，则可能开始时间很晚，也不合理。因此我们最好选择开始最早而且结束时间短的会议，即最早开始时间+持续时间最短，这不就等价于选最早结束时间嘛！是不是有点儿意思~。因此，我们采用第（3）种贪心策略。

public static int bestArrange(Program[] programs, int timePoint) {
    Arrays.sort(programs, new ProgramComparator());
    int result = 0;
    // 从左往右依次遍历所有的会议
	for (int i = 0; i < programs.length; i++) {
		if (timePoint <= programs[i].start) {
			result++;
			timePoint = programs[i].end;
		}
	}
	return result;
}

004区间调度问题

给你很多形如 [start, end] 的闭区间，请你设计一个算法，算出这些区间中最多有几个互不相交的区间。举个例子，intvs = [[1,3], [2,4], [3,6]]，这些区间最多有 2 个区间互不相交，即 [[1,3], [3,6]]，你的算法应该返回 2。注意边界相同并不算相交。
思路可以分成下面三步：
1)从区间集合中选择一个区间x，这个x是所有区间中结束最早的(end最小)。
2)把所有与x区间相交的区间从区间集合中删除掉。
3)重复1和2，直到区间集合为空。之前选出的那些x的集合就是最大的不想交子集。

public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
        return 0;
    }
    Arrays.sort(
        intervals,
        new Comparator < int[] > () {@
            Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
    //排序后的第一个必然可用
    int count = 1;
    int x_end = intervals[0][1];
    for (int[] interval: intervals) {
        if (interval[0] >= x_end) {
            count++;
            x_end = interval[1];
        }
    }
    return count;
}

005背包问题

用贪心算法实现背包问题的求解。背包容量为20；最优解为装入背包的物品价值总和最大。

基本思想：
1)计算所有物品的性价比;
2)按物品性价比从高到低装入，只有当高一级的性价比物品全部装入后，才会装入下一级的性价比物品;
3)装到最后无法全部装入该物品时进行部分装入;

public class GreedyBag { // 贪心算法解决的背包问题是可以部分装载的问题，不是0-1
    static float maxV = 20; // 最大容量
    float V; // 体积
    float worth; // 价值
    int i; // 物品编号
    float cost; // 性价比,单位体积价值
    static GreedyBag[] thing = new GreedyBag[6]; // 根据实际情况调整
    static float[] x = new float[thing.length]; // 物品i对应的数量在下标i-1
    public GreedyBag(int num, float V, float w) { // 物品信息初始化
        i = num;
        worth = w;
        this.V = V;
        cost = w / V;
        thing[i - 1] = this; // 添加进数组
    }
    public static void sort() { // 初始化满了再用的冒泡排序,性价比最小的沉底
        float smaller; // 存储更小的价值比
        for (int i = 0; i < thing.length; i++) {
            for (int j = 0; j < thing.length - i - 1; j++) {
                smaller = thing[j].cost;
                if (smaller < thing[j + 1].cost) { // 后面更大就交换
                    GreedyBag bigger = thing[j + 1];
                    thing[j + 1] = thing[j];
                    thing[j] = bigger;
                }
            }
        }
    }
    public static float knapsack() {
        float maxValue = 0;
        float v = 0; // 已装载体积
        int i;
        for (int j = 0; j < x.length; j++)
            x[j] = 0; // 物品的装载初始化为0
        for (i = 0; i < thing.length; i++) {
            if (v + thing[i].V > maxV)
                break; // 下标i的物品没法全部装下
            x[thing[i].i - 1] = thing[i].V; // 性价比高的全部装下
            v += thing[i].V;
            maxValue += thing[i].worth;
        }
        if (i < thing.length) { // 由break跳出的，部分装载
            float elseV = maxV - v;
            x[thing[i].i - 1] = elseV; // 部分装载
            v = maxV;
            maxValue += elseV / thing[i].V * thing[i].worth;
        }
        return maxValue;
    }
    public static void printX() { // 打印装载情况
        for (int i = 0; i < x.length; i++) {
            if (x[i] == 0)
                continue;
            System.out.println("物品编号" + (i + 1) + "装了体积" + x[i]);
        }
    }
    public static void main(String args[]) {
        GreedyBag i1 = new GreedyBag(1, 3, 6);
        GreedyBag i2 = new GreedyBag(2, 2, 5);
        GreedyBag i3 = new GreedyBag(3, 5, 10);
        GreedyBag i4 = new GreedyBag(4, 1, 2);
        GreedyBag i5 = new GreedyBag(5, 6, 16);
        GreedyBag i6 = new GreedyBag(6, 4, 8);
        sort(); // 根据性价比排序
        float maxValue = knapsack();
        System.out.println("最大能装价值" + maxValue + "的物品");
        printX();
    }
}