求解贪婪算法，贪婪算法的基本思想

贪婪算法基本思想是分层处理。

贪婪算法是一种分层方法。 使用贪婪的禅宗信仰方法。

设计算法的特征是一步一步，根据一定的优化度量（可能是也可能不是目标函数），并且必须在每一步获得局部最优解。 每一步只考虑一条数据，其选择应满足局部优化条件。 如果下一轮数据不再是可行的解决方案，如果无法再将数据与偏优解决方案连接起来，则在枚举所有数据之前，不会将数据添加到部分解决方案中，或者无法添加更多数据。

贪婪算法可以解决的大多数问题通常具有以下特点：

1. 随着算法的进展，将累积另外两组：一组包含已考虑和选择的候选者，另一组包含已考虑但被丢弃的候选者。

2.有一个功能可以检查一组候选对是否为问题提供了解决方案。 此功能不考虑解决方法是否最佳。

3.还有一个功能可以检查一组候选对象是否可行，即是否可以在集合中添加更多的候选对象来获得解决方案。 与前面的函数一样，此时不考虑解决方案的最优性。

4. 选择功能可以指示哪个剩余的候选对象是最有希望解决问题的对象。

5. 最后，目标函数给出了解的值。

在一定的标准下，优先考虑符合标准的样本，最后考虑不符合标准的样本，最后得到答案的算法称为贪婪算法。

也就是说，解在某种意义上是局部最优的，而不考虑整体最优。

局部最优 -？总体最佳。

有些项目需要占用会议室进行演示，会议室不能同时容纳两个项目。 给定每个项目的开始时间和结束时间（为您提供一系列特定项目），您可以安排演示的时间表，并要求会议室进行最多的演示。 回到这个数量最多的讲道。

将一根金条切成两半的成本与相同长度的铜板相同。 例如，一根长度为20的金条，无论切成两半多长，裤凳都要花费20块铜板。

一群人要分整根金条，怎么分最经济的铜板？ 例如，给定一个数组，总共代表三个人，整个金条的长度为 10+20+30=60。 金条分为三部分：10、20 和 30。

如果将长度 60 bar 分成 10 和 50，则成本为 60; 将 50 根金条的长度分成 20 和 30，成本为 50; 它总共花费了 110 块铜板。 但是如果把60根金条的长度分成30根，胡维30根，就要花60根; 然后将长度30的金条分成10和20，并花费30粗链; 它总共花费了 90 块铜板。

输入一个数组，该数组返回拆分的最小成本。

输入：正数组成本

正利润

正 k，正 m

含义：成本[i]表示项目I的成本。

利润[i]表示项目I在扣除费用后仍可赚取的金额（利润）

k 表示您最多只能在串行中执行 k 个项目。

m 表示您的初始资金。

输出：您最终获得的最大金额。

所谓贪婪选择属性，是指通过一系列局部最优选择，可以选出问题的总体最优解，也就是说，在考虑做出什么选择时，我们只考虑当前问题的最优选择，而不考虑子问题的结果。 这是贪婪算法可行的第一个基本要素。 贪婪算法以迭代方式进行连续的贪婪选择，每个贪婪选择将所需问题简化为更小的子问题。

要确定特定问题是否具有贪婪选择的性质，有必要证明在每一步中做出的贪婪选择最终导致了问题的总体最优解决方案。

当一个问题的最优解包括其子问题的最优解时，该问题被称为具有最优子结构的性质。 问题的最优子结构是贪婪算法可以解决的问题的关键特征。

需要注意的是，贪婪算法并非完全不可用，一旦贪婪策略被证明是正确的，它就是一种高效的算法。 例如用于查找最小生成树的 prim 算法和 kruskal 算法都是漂亮的贪婪算法

贪婪算法仍然是最常见的算法之一，这是由于其简单易行，构建贪婪策略并不是很困难。

不幸的是，它需要先得到证明，然后才能应用于问题的算法。

一般来说，贪婪算法的证明围绕着这样一个事实，即整个问题的最优解必须从贪婪策略中存在的子问题的最优解中获得。

对于示例中的 3 种贪婪策略，它们都无法建立（无法证明），解释如下：

贪婪策略：选择最有价值的一个。 反例：

w = 30 项：a b c

重量： 28 12 12

值： 30 20 20

根据策略，先选择A项，然后不能选择，但最好选择B和C。

2）贪婪策略：选择权重最小的。它的反例与第一种策略相似。

3）贪婪策略：选择每单位重量价值最高的物品。反例：

w = 30 项：a b c

重量： 28 20 10

值： 28 20 10

根据策略，三个项目的单位权重值相同，程序无法根据现有策略做出判断，如果选择A，答案不正确。 但是，如果在单位值相同时，优先使用小权重的条件中加入一句话，就可以解决这样的问题。

所以需要注意的是，贪婪算法可以和随机化算法一起使用，就不多说具体的例子了。 （因为这类算法的普及度不高，技术含量也非常高，所以需要通过一些反例来判断随机对象是什么，随机性程度如何，但也是草稿状态不能保证它完全正确，只能是最大状态的概率景博是正确的）。