hello算法之贪心

创建时间: 2026-07-14 09:42:25

贪心算法

贪心算法(greedy algorithm)是一种常见的解决优化问题的算法,其基本思想是在问题的每个决策阶段,都选择当前看起来最优的选择,即贪心地做出局部最优的决策,以期获得全局最优解。贪心算法简洁且高效,在许多实际问题中有着广泛的应用。

贪心算法和动态规划都常用于解决优化问题。它们之间存在一些相似之处,比如都依赖最优子结构性质,但工作原理不同。

  • 动态规划会根据之前阶段的所有决策来考虑当前决策,并使用过去子问题的解来构建当前子问题的解。
  • 贪心算法不会考虑过去的决策,而是一路向前地进行贪心选择,不断缩小问题范围,直至问题被解决。

我们先通过例题“零钱兑换”了解贪心算法的工作原理。

给定n种硬币,第i种硬币的面值为coins[i-1],目标金额为amt,每种硬币可以重复选取,问能够凑出目标金额的最少硬币数量。如果无法凑出目标金额,则返回-1

int coinChangeGreedy(vector<int> &coins, int amt) {
	int i = coins.size() - 1;
	int count = 0;
	while(amt > 0) {
		while(i > 0 && coins[i] > amt) {
			i--;
		}
		amt -= coins[i];
		count++;
	}
	return amt == 0 ? count : -1;
}