。

贪心算法在有最优子结构的问题中尤其有效#xff0c;这意味着局部最优解能决定全局最优解。

简单来说#xff0c;贪心…贪心算法是一种在每一步选择中都采取在当前状态下最好或最优即最有利的选择从而希望导致结果是全局最好或最优的算法。

贪心算法在有最优子结构的问题中尤其有效这意味着局部最优解能决定全局最优解。

简单来说贪心算法对每个子问题都做出选择不能回退这与动态规划不同后者会保存以前的结果并根据以前的结果对当前进行选择有回退功能。

局部最优选择在每一步都做出在当前看来最优的选择希望这些局部最优能导致全局最优解。

无回退操作一旦做出了选择就不再回退即不考虑以前的选择。

贪心算法适用于具有“贪心选择性质”的问题即局部最优解能决定全局最优解。

贪心算法不能保证求得的最后解是最佳的也不能用来求最大或最小解的问题只能求满足某些约束条件的可行解的范围。

找零问题如何用最少的硬币找零。

最小生成树如Kruskal算法和Prim算法。

单源最短路径如Dijkstra算法。

任务调度问题如何安排任务以减少等待时间或延迟。

压缩编码如Huffman编码。

建立数学模型来描述问题。

把求解的问题分成若干个子问题。

对每一子问题求解得到子问题的局部最优解。

把子问题的解局部最优解合成原来解问题的一个解。

虽然贪心算法相对简单易懂但它并不总是能得到全局最优解因此在使用时需要仔细分析问题是否适合采用贪心算法。

贪心算法可以用来解决背包问题的一种特殊形式——分数背包问题Fractional

Knapsack

Problem但对于经典的0-1背包问题贪心算法通常无法保证找到最优解。

分数背包问题

在分数背包问题中你可以将物品分割成任意大小然后选择其中的一部分放入背包中目标是最大化背包中物品的总价值同时不超过背包的容量限制。

对于这个问题贪心算法是有效的因为你可以按照物品的价值重量比单位价值来选择物品优先选择单位价值最高的物品直到背包装满为止。

0-1背包问题

对于0-1背包问题每个物品只能整体选取或不选取不能分割。

这种情况下贪心算法选择物品的策略可能无法得到最优解。

例如如果贪心算法只考虑物品的价值或重量而不是价值重量比那么它可能会错过更优的组合因为一个轻而价值高的物品可能比几个重而价值低的物品更有价值。

对于0-1背包问题最优解可能需要通过动态规划等方法来找到因为贪心算法可能无法考虑到所有物品组合的总价值。

总结贪心算法适用于分数背包问题但对于0-1背包问题它可能无法保证找到最优解。

以下是使用贪心算法解决分数背包问题的C语言实现。

在这个实现中我们首先根据物品的价值重量比单位价值对物品进行排序然后按单位价值从高到低依次选择物品放入背包直到背包容量达到限制。

#include

}这段代码首先定义了一个Item结构体来存储每个物品的重量、价值和价值重量比。

compare函数用于根据价值重量比对物品进行降序排序。

fractionalKnapsack函数实现了贪心算法首先对物品按价值重量比进行排序然后遍历排序后的物品数组根据背包剩余容量决定是否将当前物品整个或部分加入背包。

最后函数返回背包中物品的最大总价值。