前言

贪心算法，又叫做贪婪算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。

比如在一般背包问题中，可以用贪心算法求解，每次选择重量小的物品优先，或者是价值高的物体优先。（这里的背包问题，不是0-1背包问题，0-1背包问题需要通过动态规划来求解。）

贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是通过局部最优解来决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。

贪心算法和之前写过的文章动态规划非常类似，不同点在于它对每个子问题的解决方案都做出选择，不能回退。动态规划会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码等

对于其他问题，贪心法一般不能得到我们要的答案。所以一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最优解。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。

实现细节

1. 创建数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来解问题的一个解。

接下来用一个示例描述贪心算法是如何解决问题的。

警察抓小偷问题。

假定警察和排成一个队列，每个警察只能抓到一个小偷，警察抓不到距离警察超过K个单位的小偷。需要找出的是抓到小偷的最大数量。

输入：arr[] = {'P', 'T', 'T', 'P', 'T'},
            k = 1。
输出：2。
最多可以抓到 2 个小偷，
警察抓到第一个小偷
第二个警察可以抓到第二个或第三个小偷。

输入：arr[] = {'T', 'T', 'P', 'P', 'T', 'P'},
            k = 2。
输出：3。

接下来看一下代码实现。

Java示例

import java.util.*;
import java.io.*;
 
class GFG
{
    // 返回可以被抓到小偷的数量
    static int policeThief(char arr[], int n, int k)
    {
        int res = 0;
        ArrayList<Integer> thi = new ArrayList<Integer>();
        ArrayList<Integer> pol = new ArrayList<Integer>();
 
        // 在 ArrayList 中存储索引
        for (int i = 0; i < n; i  ) {
            if (arr[i] == 'P')
            pol.add(i);
            else if (arr[i] == 'T')
            thi.add(i);
        }
 
        // 当前距离警察最近的小偷
        // 小偷: thi[l], 警察: pol[r]
        int l = 0, r = 0;
        while (l < thi.size() && r < pol.size()) {
 
            // 可以被抓的小偷
            if (Math.abs(thi.get(l) - pol.get(r)) <= k) {
            res  ;
            l  ;
            r  ;
            }
             
            // 增加最小索引
            else if (thi.get(l) < pol.get(r))
                l  ;
            else
                r  ;
        }
        return res;
    }
 
    public static void main(String args[])
    {
        int k, n;
        char arr1[] =new char[] { 'P', 'T', 'T',
                                  'P', 'T' };
        k = 2;
        n = arr1.length;
        System.out.println("最多抓到： "
                             policeThief(arr1, n, k));
                             
        char arr2[] =new char[] { 'T', 'T', 'P', 'P',
                                  'T', 'P' };
        k = 2;
        n = arr2.length;
        System.out.println("最多抓到： "
                             policeThief(arr2, n, k));
    }
}

输出：

最多抓到：2

最多抓到：3

性能

时间复杂度：O(N)，空间复杂度O(1)

这篇好文章是转载于：学新通技术网