贪心算法

贪心算法，又称贪婪算法（Greedy Algorithm），是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优解出发来考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法适用范围：
局部最优策略能导致产生全局最优解

基本思路

• 建立数学模型来描述问题
• 把求解的问题分成若干个子问题
• 对每个子问题求解，得到子问题的局部最优解
• 把子问题的解局部最优解合成原来问题的一个解

框架

从问题的某一初始解出发；
while （朝给定总目标前进一步）
{
利用可行的决策，求出可行解的一个解元素；
}
由所有解元素组合成问题的一个可行解；

实例

纸币找零问题

假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？

public class GiveMoney {

    private final static int[] level = new int[]{1, 2, 5, 10, 20, 50, 100};

    public TreeMap<Integer, Integer> give(int money) {
        if (money <= 0) {
            throw new RuntimeException("invalid parameters");
        }

        TreeMap<Integer, Integer> result = new TreeMap<>();
        for (int i = level.length - 1; i >= 0; i--) {
            int count = money / level[i];
            money %= level[i];
            result.put(level[i], count);
        }
        return result;
    }
}

背包问题

有一个背包，背包容量是W=150，有7个物品，每个物品有各自的重量和价值，每个物品有一件，要求尽可能让装入背包中的物品总价值最大，但不能超过总容量

物品	A	B	C	D	E	F	G
重量	35	30	60	50	40	10	25
价格	10	40	30	50	35	40	30

考虑使用贪心求解，使用贪心策略：
每次挑选价值最大的物品放入背包，得到的结果是否最优？
每次挑选所占重量最小的物品放入背包，得到的结果是否最优？
每次选取单位重量价值最大的物品，得到的结果是否最优？

显然，以上三种策略都无法成立，所以该问题不能用贪心算法求解
这个问题是属于0-1背包问题，普通背包问题可以使用贪心算法来解决

普通背包问题和0-1背包问题差不多，0-1背包的每件物品只有一件，而普通背包的每件物品数量是不止一件的，如果每件物品的数量是无限的，那这种称为完全背包问题