阅读 485

【译】贪心算法,你入门了吗?

贪心算法,你入门了吗?

贪心算法在大多数情况下都易于实现,在求解最优问题时,也是最常用的编码套路之一,而且它的资源消耗也比较低。

不过这个算法也有缺点,它不能保证每次都能找到最优解,有时候只能找到接近最优解的方案。不管怎样,在很多情况下,接近最优解就足够了。

这个算法一般是对规模为 “n” 的问题迭代 “n” 次,所以它的复杂度可能是 O(n),O(n × log(n)),但是不会超过 O(n²)。

这个算法能解决的大多数问题都有以下两个特性:

  1. 贪心属性:它的意思是每次迭代时都采用局部最优解,而无需考虑对全局的影响。我们相信通过不断求解局部最优解终会得到全局最优解,但是正如我之前所说,这个结论不一定成立。为了证明在每次迭代中都求得了最优解,我们需要使用归纳法(显然不是简单的证明)。
  2. 最优子结构: 我之前提到过一些。求解的问题必须能划分为子问题,每个子问题都有最优解。

本文中,我们将学习如何编写自己的贪心算法,然后用这个算法解决一个非常著名的难题。

贪心算法通用模版 (Java)

public ArrayList greedy(ArrayList candidates) {
    solution;
    while (!isSolution(solution) && (candidatesLeft(candidates)) {
            cadidate = selectCandidate(candidates);
            removeCandidate(candidate, candidates);
            if (isGoodCandidate(candidate, solution)) {
                addCandidate(candidate, solution);
            }
        }
        if (isSolution(solution)) {
            return solution;
        } else {
            return null;
        }
    }
}
复制代码

在解释代码之前,我先给出一些在伪代码中用到的术语的定义。

  1. Candidates: 所有可能的解集。它可以是任意的数据类型,但通常是可迭代的。在我们处理示例问题时,会加深对它的理解。现在请先记住结论 😁。
  2. Candidate: 在解集中,我们当前选中的一个解。
  3. Solution: 解变量的第一个实例只需是一种数据结构,在这里我们将存储当前的解。
  4. isSolution, candidatesLeft, removeCandidate, addCandidate, isGoodCandidate: 这些也是我们要创建的方法,其中的某些方法在一些实际问题中不必是完整的,但是为了总结代码模版,我把它们全部定义为方法。

首先,我们初始化解的数据结构,它可以是数组,布尔值,整数…… 我们只需要声明一下。

solution
复制代码

然后,我们看一下这个 while 循环,它的循环条件中有两个方法。这些方法必须编写,但有时并不需要完整的方法体,例如,判断是否有剩余备选解的这个方法。

while (!isSolution(solution) && (candidatesLeft(candidates))
复制代码

当我们发现当前尚未找到解,并且有剩余备选解可以尝试时,我们将选择一个备选解,并立即将其从我们的备选解集中删除。

cadidate = selectCandidate(candidates);
removeCandidate(candidate, candidates);
复制代码

下一步很简单。如果候选解是正确的解,则只需将其添加到解结构中。

if (isGoodCandidate(candidate, solution)) { 
    addCandidate(candidate, solution); 
}
复制代码

然后,我们只需检查问题是否已达到解决的状态,然后将解返回。

if (isSolution(solution)) { 
    return solution; 
} else { 
    return null; 
}
复制代码

至此我们已经看完了代码并对其进行了粗略的解释,现在我给您出道题,请您尝试自己解答。这是一个众所周知的问题,在网上很容易就能搜到答案,但我建议您还是尝试自己解决。


零钱兑换的问题

有6种硬币,每种硬币的值分别为 {50,20,10,5,2,1},它们按递减排序作为参数传递。 每种硬币都可能成为我们的候选解。您必须找到一种最佳的兑换方式。(用最少的硬币找零

示例输入: 15(我们必须以最少的硬币数量凑齐 15 并返回硬币集合

示例输出: 10、5(我们返回了和为 15 的硬币集合,且硬币数量最少

在这个确定的硬币系统 {50,20,10,5,2,1} 中,该算法能找到最优解,但是请注意,如果候选解发生改变,可能会导致该算法无法找到最优解。

提示

如果您没有足够努力尝试,就不应该看这一段内容 🤨…… 开个玩笑,继续吧,我确信我希望您已经学到了一些新知识 😄。

  • selectCandidate() 方法中,首先选择面额最大的硬币,然后用较小的硬币填充剩余的零钱。在这个过程中,您要一直检查是否超出剩余的零钱。

解法

我提供的解法用 Java 编写的,其中用到了面向对象的知识。

public class Coin {
    private int value;
    private int quantity;
    Moneda(int value, int quantity) {
        this.value = value;
        this.quantity = quantity;
    }
    /* getters & setters */
}

/* This is actually the "hard" part */
int selectCandidate(ArrayList < Integer > values) {
    int biggest = Integer.MIN_VALUE;
    for (Integer coin: values)
        if ((biggest < coin)) biggest = coin;
    return biggest;
}

/* Now the actual schema */

ArrayList < Coin > greedySchema(ArrayList < Integer > values, int quantity) {
    /* We initialize our solution structure */
    ArrayList < Coin > solution = new ArrayList < Coin > ();
    /* Any auxiliary variable is ok */
    int value;
    
    while ((quantity > 0) && (!values.isEmpty())) {
        /* Select and remove the coin from our monetary system */
        value = selectCandidate(values);
        values.remove(new Integer(value));
        
        /* If this is true, it meanwe can still look for coins to give */
        if ((quantity / value) > 0) {
            solution.add(new Coin(value, quantity / value));
            /* This will lower the quantity we need to give back */
            quantity = quanity % value;
        }
    }
    
    /* Once the quantity is 0 we are DONE! */
    if (quantity == 0) {
        return solution;
    } else return null;
}
复制代码

资源

如果您喜欢贪心算法的工作原理,并且想深入研究,请访问 Hackerrank 或者 Hackerearth,这里有有很多要解决的问题,我相信您已经对它们有一定了解 😊。

有时,我个人也会把 GitHub 作为搜索引擎,并简单地写下我寻找的主题 [贪心算法]。

结论

综上所述,即使对于简单的个人项目,贪心算法也能表现优异,它不需要你花费太多时间去思考,并且只消耗很少的资源。而且,使用贪心算法可以轻松解决很多面试问题。大多数时候,使用贪心或动态规划都可以满足内存和复杂度方面的要求,但这就是另一个话题了 😉。

感谢您的阅读,欢迎评论 😄。

如果发现译文存在错误或其他需要改进的地方,欢迎到 掘金翻译计划 对译文进行修改并 PR,也可获得相应奖励积分。文章开头的 本文永久链接 即为本文在 GitHub 上的 MarkDown 链接。


掘金翻译计划 是一个翻译优质互联网技术文章的社区,文章来源为 掘金 上的英文分享文章。内容覆盖 AndroidiOS前端后端区块链产品设计人工智能等领域,想要查看更多优质译文请持续关注 掘金翻译计划官方微博知乎专栏

关注下面的标签,发现更多相似文章
评论