贪心算法详解：原理、应用场景及代码实现

贪心算法详解：原理、应用场景及代码实现

引用

CSDN

1.

https://blog.csdn.net/2301_79602614/article/details/138244968

贪心算法是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望导致结果是最好或最优的算法。这种算法通常用于求解优化问题，如最小生成树、背包问题等。

贪心算法的基本概念

贪心算法的核心思想可以概括为以下三个步骤：

1. 将寻找最优解的问题分为若干个步骤
2. 每一步骤都采用贪心原则，选取当前最优解
3. 因为没有考虑所有可能，局部最优的堆叠不一定让最终解最优

贪心算法的应用场景包括：

1. 背包问题：给定一组物品和一个背包，每个物品有一定的重量和价值，要求在不超过背包容量的情况下，尽可能多地装入物品。
2. 活动选择问题：在一个活动集合中，每次只能参加一个活动，问如何安排时间以最大化所有活动的收益。
3. 编辑距离问题：给定两个字符串，求它们之间的最小编辑距离（即将一个字符串转换为另一个字符串所需的最少操作次数）。
4. 网络流问题：给定一张有向图和一些起点和终点，求最大流量。
5. 找零问题：给定一定数量的硬币和需要找零的金额，求使用最少的硬币数。

贪心算法的常见问题及解答

1. 贪心算法一定会找到最优解吗？

• 答：不一定。贪心算法只保证在每一步选择中都是最优的，但并不能保证整个问题的最优解。例如，背包问题中的贪心算法可能会导致最后一个物品没有被装入背包。

2. 如何判断一个问题是否适合用贪心算法解决？

• 答：一个问题如果可以用递归的方式分解成若干个子问题，且每个子问题都有明确的最优解（即局部最优），那么这个问题就可以用贪心算法解决。

3. 贪心算法的时间复杂度是多少？

• 答：贪心算法的时间复杂度取决于问题的规模和具体实现。一般来说，对于规模较小的问题，贪心算法的时间复杂度可以达到O(nlogn)或O(n^2)；对于规模较大的问题，可能需要O(n^3)或更高。

贪心算法的具体实现

Dijkstra算法

while (!list.isEmpty()) {
    // 选取当前【距离最小】的顶点
    Vertex curr = chooseMinDistVertex(list);
    // 更新当前顶点邻居距离
    updateNeighboursDist(curr);
    // 移除当前顶点
    list.remove(curr);
    // 标记当前顶点已经处理过
    curr.visited = true;
}

需要注意的是，当图中存在负边时，Dijkstra算法可能无法得到正确的最短路径解。这是因为贪心原则会认为本次已经找到了该顶点的最短路径，下次不会再处理它（curr.visited = true）。相比之下，Bellman-Ford算法不会出错，因为它每次都处理所有边，但效率不如Dijkstra算法。

Prim算法

while (!list.isEmpty()) {
    // 选取当前【距离最小】的顶点
    Vertex curr = chooseMinDistVertex(list);
    // 更新当前顶点邻居距离
    updateNeighboursDist(curr);
    // 移除当前顶点
    list.remove(curr);
    // 标记当前顶点已经处理过
    curr.visited = true;
}

Kruskal算法

while (list.size() < size - 1) {
    // 选取当前【距离最短】的边
    Edge poll = queue.poll();
    // 判断两个集合是否相交
    int i = set.find(poll.start);
    int j = set.find(poll.end);
    if (i != j) { // 未相交
        list.add(poll);
        set.union(i, j); // 相交
    }
}

其他贪心算法的例子

• 选择排序、堆排序
• 拓扑排序
• 并查集合中的 union by size 和 union by height
• 哈夫曼编码
• 钱币找零（change-making problem）
• 任务编排
• 求复杂问题的近似解

零钱兑换问题

零钱兑换II（LeetCode 518）

这是一个典型的动态规划问题，但也可以用贪心算法来尝试解决。下面是一个暴力递归的实现：

public int rec(int index, int[] coins, int remainder) {
    // 1.情况1:剩余金额 < 0 - 无解
    // 2.情况2:剩余金额 > 0 - 继续递归
    // 3.情况3:剩余金额 = 0 - 有解
    if (remainder < 0) {
        return 0;
    } else if (remainder == 0) {
        return 1;
    } else {
        int count = 0;
        for (int i = index; i < coins.length; i++) {
            count += rec(i, coins, remainder - coins[i]);
        }
        return count;
    }
}

但是这个代码在LeetCode上运行会超时，因为重复处理了很多次相同的操作。我们可以考虑用记忆化搜索或动态规划来优化。

零钱兑换（LeetCode 322）

这是一个求最小硬币数的问题，可以用动态规划来解决。下面是一个暴力递归的实现：

static int min = -1; // 需要的最少硬币数  2 3
public int coinChange(int[] coins, int amount) {
    rec(0, coins, amount, new AtomicInteger(-1), new LinkedList<>(), true);
    return min;
}

// count 代表某一组合 钱币的总数 可变的整数对象
public void rec(int index, int[] coins, int remainder, AtomicInteger count, LinkedList<Integer> stack, boolean first) {
    if (!first) {
        stack.push(coins[index]);
    }
    count.incrementAndGet(); // count++
    if (remainder == 0) {
        System.out.println(stack);
        if (min == -1) {
            min = count.get();
        } else {
            min = Integer.min(min, count.get());
        }
    } else if (remainder > 0) {
        for (int i = index; i < coins.length; i++) {
            rec(i, coins, remainder - coins[i], count, stack, false);
        }
    }
    count.decrementAndGet(); // count--
    if (!stack.isEmpty()) {
        stack.pop();
    }
}

贪心法求解零钱兑换（LeetCode 322）

贪心法在某些情况下可以快速得到解，但并不保证总是能得到最优解。下面是一个贪心算法的实现：

public int coinChange(int[] coins, int amount) {
    int remainder = amount;
    int count = 0;
    for (int coin : coins) {
        while (remainder - coin > 0) {
            remainder -= coin;
            count++;
        }
        if (remainder - coin == 0) {
            remainder = 0;
            count++;
            break;
        }
    }
    if (remainder > 0) {
        return -1;
    } else {
        return count;
    }
}

需要注意的是，贪心算法在某些情况下可能会得到错误的解，因为它没有考虑所有可能的组合。例如，对于输入[15, 10, 1]和金额21，贪心算法会得到错误的解，因为它没有“回头”机制来检查更优的组合。