5.2 贪心算法的理论基础

在寻找最优解的问题中，按照一定的贪心准则，从问题的初始状态出发，直接寻求每一步的最优解，最后通过几次贪心得到整个问题的最优解选择，这个解决方案是贪心算法。

当问题具有最优子结构和贪心选择的性质时，贪心算法通过一系列的选择得到问题的解。

5.2 贪心算法的理论基础

贪心算法是在每一步选择中，在当前状态下取最佳或最优选择的算法，即贪心选择，使得期望的结果是最好或最优的算法。

5.2.1 个贪心选择属性

贪心选择的性质是指可以通过一系列局部最优选择得到期望的问题，即贪心选择。这是贪心算法起作用的第一个基本要素，也是贪心算法和动态规划算法之间的主要区别。

在动态规划算法中，每一步的选择往往取决于相关子问题的解，所以只有在相关子问题解决后才能做出选择。

在贪心算法中，只在当前状态下做出最优选择，即局部最优选择，然后求解该选择形成的对应子问题。贪心算法做出的贪心选择可以取决于前几年做出的选择，但绝不取决于未来做出的选择，也不会取决于子问题的解决方案。

由于这些差异，动态规划算法一般采用自下而下的方法解决每个子问题，而贪心算法则采用自上而下的方法贪心是什么意思，以迭代的方式进行连续的贪心选择。贪心选择将问题简化为更小的子问题。

5.2.2个最优子结构属性

当问题的最优解包含其子问题的解时，称该问题具有最优子结构性质。

贪心算法的每个操作都会对结果产生直接影响，而动态规划则不会。贪心算法选择每个子问题的解决方案贪心是什么意思，不能回头；动态规划根据之前的选择选择当前的解，并具有回退的功能。

动态规划主要用于二维或三维问题，而贪心算法通常用于一维问题。

5.2.3 贪心算法的求解过程

使用贪心算法需要考虑以下几个方面：

候选集A

解集S

解函数解

选择功能选择

可行函数可行

算法5.2 贪心算法的通常流程

// A是问题的输入集合，即候选集合
Greedy(A){
    S = {}; // 初始解集为空
    while (not solution(S)){ // 集合S没有构成一个解
        x = select(A); // 在候选集A中做贪心选择
        if (feasible(S, x)) // 判断集合S中加入x是否可行
            S += {x}; // 在集合S中加入{x}
        A -= {x}; // 候选集A中删去{x}
    }
    return S;
}