贪心算法 的基本思路是在对问题进行求解的时总是做出当前看来最好的选择,即不从整体进行考虑,所作出的仅是在某种意义上的局部最优解。通常,我们希望找到问题的最优解,那么贪心法是不是没有意义的?答案是否定的。这是因为在某些求解问题中,当满足一定条件时,这些局部最优解就转变成了整体最优解,所以贪心法的困难部分就是要证明所设计的苏纳法确实是整体最优解,或者求解了它要解决的问题。

在求解问题时,通常求解问题直接给出或者可以分析出某些约束条件,满足约束条件的问题的解称为 可行解 。另外求解问题直接给出或者可以分析出衡量可行解好坏的 目标函数 ,使目标函数最大或最小的可行解称为 最优解

贪心法从某个初始空解出发,采用逐步构造最优解的方法向给定的目标前进,每一步决策产生n元组解的一个分量。每一步用作决策依据的选择准则称为 贪心准则 ,也就是说,添加解分量形成的 部分解 不违反可行解约束条件。每一次贪心选择都将所求的问题简化为规模更小的问题,并希望通过每次所做的局部选择产生一个整体最优选择。

求解过程

SolutionType Greedy(SType a[], int n) {
    // 解向量(x0, x1, x2, ..., xn)类型为SolutionType, 分量为SType
    SolutionType x = {}; // 初始化解向量不含任何分量
    for (int i = 0; i < n; i++) {
        SType xi = Select(a); // 从输入a中选择一个当前最好的分量
        if (Feasiable(xi)) { // 判断xi是否包含在当前解中
            solution = Union(x, xi); // 将xi分量与x合并形成x
        }
    }

    return x;
}